Determinants and invertibility of circulant matrices

1.   Introduction

Circulant matrices are a kind of important patterned matrix which arises in many areas of physics, molecular vibration, signal processing, image processing, digital image disposal, error correcting code theory, and applied mathematics ^[1,2,3]. Consequently, there are many papers that investigated the properties and applications of circulant matrices. In order to better understand the essence of circulant matrices, in recent years, some scholars have tried to provide an effective expression for the determinant, the eigenvalues, and the corresponding inverses, see for instance ^[4,5,6,7]. On the other hand, the invertibility of circulant matrices has been widely studied in the literature by using the primitive $n$-th root of unity and some associated polynomial, see ^[7,8]. In fact, circulant matrices $Circ(a_0, a_1, \cdots, a_{n-1})$ are invertible if and only if $f(\varepsilon ^j)\neq 0$ for every $0\leq j \leq n-1$, where $f(x) = \Sigma ^{n-1}_{j = 0}a_jx^j$ and $\varepsilon$ is a primitive $n$-th root of unity. However, it is not easy to count the product $f(\varepsilon ^0)f(\varepsilon)\cdots f(\varepsilon ^{n-1})$, see ^[4]. Therefore, it is important to either reduce the calculation of $f(\varepsilon ^0)f(\varepsilon)\cdots f(\varepsilon ^{n-1})$ or to provide other criteria for discrimination. Recently, the authors in ^[4] investigated circulant matrices of type $Circ(a, b, c, \cdots, c)$ and $Circ(a, b, c, \cdots, c, b)$ and provided some necessary and sufficient conditions for its invertibility. Furthermore, they explicitly obtained a closed formula for the inverse matrices of these type of circulant matrices.

In this paper, we first consider circulant matrices of type $Circ(a_0, a_1, \cdots, a_{n-1})$ with $a_0, a_1, \cdots, a_{n-1}$ a strictly monotonic sequence. This type of matrix arises in the study of sum systems and sum circulant matrices. A sum system is a collection of finite sets of integers such that the sums formed by taking one element from each set generates a prescribed arithmetic progression, and a sum circulant matrix whose left and right circulant parts take their entries from the two component sets of a sum system has consecutive integer entries, for example, see ^[9,10,11]. We prove that this kind of circulant matrix must be invertible. Next, we hope to reduce the calculation of $f(\varepsilon ^0)f(\varepsilon)\cdots f(\varepsilon ^{n-1})$ for a prime $n$ by using the techniques on finite fields to calculate the determinant of a circulant matrix by a simple program. Finally, we provide two examples to explain how to use the obtained results to calculate the determinant of a circulant matrix.

2.   Prelemanery

In this section, we recall some basic concepts and provide some results needed during the proof of our main theorems.

A matrix $A = (a_{ij})$ is said to be circulant (or right circulant) with parameters $a_0, \cdots, a_{n-1}$ if

It is usually abbreviated as $A = Circ(a_0, a_1, \dots, a_{n-1})$. It is clear that $Circ(a_0, a_1, \dots, a_{n-1}) = a_0P^0+a_1P^1+a_2P^2+ \ldots +a_{n-1}P^{n-1}$ with $P = Circ(0, 1, 0, \ldots, 0)$ and $P^0 = I$.

Let $\varepsilon$ be a primitive $n$-th root of unity. Then, $1 = \varepsilon ^0, \varepsilon, ..., \varepsilon ^{n-1}$ are different from each other, that is, they are just all $n$-th roots of unity.

The following results are well-known, and can be found in ^[2].

Lemma 2.1. Let $A = Circ(a_0, a_1, \dots, a_{n-1})$ be a circulant matrix, $\varepsilon$ be a primitive $n$-th root of unity, and $f(x) = \Sigma ^{n-1}_{j = 0}a_jx^j$. Then,

1) $|A| = \Pi ^{n-1}_{j = 0} f(\varepsilon ^j)$;

2) $A$ is invertible if and only if $f(\varepsilon ^j)\neq 0$ for $j = 0, 1, \cdots, n-1$; and

3) If $A$ is invertible, then the inverse $A^{-1}$ of $A$ is also a circulant matrix.

Lemma 2.2. Let $n$ be a prime and $\varepsilon$ be a $n$-th root of unity with $n\neq 1$. Then,

1) $\varepsilon$ must be a primitive $n$-th root of unity, and therefore $1 = \varepsilon ^0, \varepsilon, ..., \varepsilon ^{n-1}$ are all $n$-th roots of unity.

2) $Z_n = Z/\langle n\rangle$ is a field.

3.   Circulant matrices $Circ(a_0, a_1, \dots, a_{n-1})$ with $a_0, a_1, \dots, a_{n-1}$ a strictly monotonic sequence

In this section, we prove that circulant matrices $Circ(a_0, \dots, a_{n-1})$ must be invertible if $a_0, \dots, a_{n-1}$ is a strictly monotonic sequence and $a_0+a_1+\dots+a_{n-1}\neq 0$. If $a_0, a_1, \dots, a_{n-1}$ are complex, then we also provide a condition for $Circ(a_0, \dots, a_{n-1})$ to be invertible.

Lemma 3.1. Let $z$ and $w$ be two non-zero complex numbers. Then, $|z+w| = |z|+|w|$ if and only if $z/w > 0$.

Proof. In fact, since $(|z|+|w|)^2 = |z|^2+2|z||w|+|w|^2$ and $|z+w|^2 = (z+w)(\bar{z}+\bar{w}) = |z|^2+\bar{z}w+z\bar{w}+|w|^2$, we see $|z+w| = |z|+|w|$ if and only if $Re(\bar{w}z) = |z||w| = |\bar{w}z|$. Additionally, $Re(\bar{w}z) = |z||w| = |\bar{w}z|$ if and only if $z/w > 0$. The proof is complete.

□

Lemma 3.2. Let $z_1$ and $z_2$ be two non-zero complex numbers. Then, $|z_1+z_2| = |z_1|+|z_2|$ if and only if there is a complex number $z$ and the real numbers $t_1 > 0$ and $t_2 > 0$ such that $z_1 = t_1z$, $z_2 = t_2z$.

Proof. It is an immediate consequence of Lemma 3.1. □

Lemma 3.3. Let $z_1, z_2, \dots, z_s$ be non-zero complex numbers. Then, $|z_1 + z_2 + \dots + z_s| = |z_1| + |z_2| + \dots + |z_s|$ if and only if there is a complex number $z$ and the real numbers $t_j > 0$ such that $z_j = t_jz$ $(j = 1, 2, \dots, s)$.

Proof. The sufficiency clearly holds; therefore, we only need to prove the necessity. Since $|z_1|+\dots+|z_s| = |z_1 +\dots+ z_s| \leq |z_1| + |z_2 + \dots + z_s| \leq |z_1| + \dots+|z_s|$, we see the following:

and

By Lemma 3.2, there are $m_1 > 0, m_2 > 0$, and a complex number $u$ such that $z_1 = m_1u, z_2 +\dots+z_s = m_2u.$

By induction, there is a complex number $z$ and real numbers $t_j > 0$ such that $z_j = t_jz$ $(j = 2, \dots, s).$

Obviously $u \ne 0 \ne z$, and

By Lemma 3.1, we see $u/z > 0$, therefore, $t_1 = m_1(u/z) > 0$ and $z_1 = t_1z.$ □

Lemma 3.4. Let $f(x) = z_0+z_1x+\dots +z_{n-1}x^{n-1}$ be a complex coefficient polynomial with $n > 2$, $\varepsilon$ be a root of $x^n = 1$, and $\varepsilon \ne 1.$ If there exist real numbers $t_j > 0$ and a non-zero complex number $z$ such that $z_j - z_{j+1} = t_jz$ $(j = 0, 1, \dots, n -2)$, then $f(\varepsilon) \ne 0.$

Proof. Let $S_0 = 1, S_k = 1 + \varepsilon + \dots+\varepsilon ^ k$ for $k = 1, 2, \dots, n - 1.$ Then, the following holds:

Noticing that $(1 + \varepsilon + \dots+\varepsilon^{n-1})(1 - \varepsilon) = 1 - \varepsilon ^n = 0$ and $\varepsilon \ne 1,$ we see $S_{n-1} = 1 + \varepsilon + \dots+\varepsilon^{n-1} = 0.$ Therefore,

Since $\varepsilon$ is a root of $x^n = 1$ and $\varepsilon \ne 1$, $\varepsilon$ is either $-1$ or a complex number; therefore, $(z_1- z_2)\varepsilon /(z_0 - z_1) = t_1\varepsilon/t_0$ is either negative or a complex number. By using Lemma 3.3, we have the following:

Now, by the hypothesis and Lemma 3.3, we observe the following: $|(z_0 - z_1)| + |(z_1 - z_2)| + \dots + |(z_{n-2} - z_{n-1})|$ = $|(z_0 - z_1) + (z_1 - z_2) + \dots + (z_{n-2} - z_{n-1})| = |z_0 - z_{n-1}|,$ so

Hence, $f(\varepsilon) \ne 0.$ □

Corollary 3.1. Let $f(x) = a_0 + a_1x +\dots + a_{n-1}x^{n-1}$ be a real coefficient polynomial with $n > 2$, $\varepsilon$ be a root of $x^n = 1$, and $\varepsilon\ne 1$. If the sequence $a_0, a_1, \dots, a_{n-1}$ is either strictly increasing or strictly decreasing, then $f(\varepsilon) \ne 0.$

Proof. It is immediate consequence of Lemma 3.4. □

By Lemma 3.4 and Corollary 3.1, we may state our main results in this section.

Theorem 3.1. Let $A = Circ(a_0, a_1, \dots, a_{n-1})$ be a circulant matrix with $a_0+a_1+ \dots +a_{n-1}\neq 0$.

1) If $a_0, a_1, \dots, a_{n-1}$ are real numbers and the sequence $a_0, a_1, \dots, a_{n-1}$ is either strictly increasing or strictly decreasing, then $A$ is invertible.

2) If $a_0, a_1, \dots, a_{n-1}$ are complex numbers and there exist real numbers $t_j > 0$ and a non-zero complex numbers $z$ such that $a_j - a_{j+1} = t_jz$ $(j = 0, 1, \dots, n -2)$, then $A$ is invertible.

4.   Circulant matrices with a prime order

In this section, we always assume that $a_0, a_1, \cdots, a_{n-1}$ is a sequence of real numbers and that $A = Circ(a_0, a_1, \cdots, a_{n-1})$ is a circulant matrix with a prime $n$. We try to reduce the calculation of $f(\varepsilon ^0)f(\varepsilon) \cdots f(\varepsilon ^{n-1})$, where $\varepsilon$ is an $n$-th root of unity with $\varepsilon \neq 1$ and $f(x) = \Sigma ^{n-1}_{j = 0}a_jx^j$. It is clear that $f(\varepsilon ^0)f(\varepsilon) \cdots f(\varepsilon ^{n-1})$ is easy to calculate for either $n = 2$ or $n = 3$. Now, we assume that $n\geq 5$. For clarity, we first recall

with

Noticing that $\{ (\varepsilon^j)^k | 0\leq k \leq n-1 \} = \{ 1, \varepsilon, \cdots, \varepsilon^{n-1} \}$ for every $1\leq j \leq n-1$, we see that every $f(\varepsilon^j)$ can be seen as an $n-1$-degree polynomial in variable $\varepsilon$. Then, $\Delta$ is an algebraic sum containing $n^n$ items, in which each term is the product of $n$ monomials and every monomial comes from one and only one in $f(\varepsilon^j)$ for $j = 0, 1, \cdots, n-1$. Thus, the coefficient of each term in $\Delta$ can be written as follows:

where $a_{k_j}$ is the coefficient of $(\varepsilon^j)^{k_j}$ in $f(\varepsilon^j)$. We should notice that $a_{k_j}$ can take values of $a_0, a_1, \dots, a_{n-1}$ for every $0\leq j\leq n-1$ and the subscript ${k_j}$ in $a_{k_j}$ only indicates that $a_{k_j}$ is taken from a certain coefficient of $f(\varepsilon^j)$. In this case, the corresponding degree of $\varepsilon$ for this term in $\Delta$ is $0 \times k_0 +1 \times k_1 +\dots + i \times k_i +\dots+(n-1) \times k_{n-1} (mod n)$. In other words, every term and the corresponding coefficient of the term in $\Delta$ satisfies the following:

For simplicity, we use $[i; k_0, k_1, \dots, k_{n-1}]$ to represent $0 \times k_0 +1 \times k_1 +2 \times k_2 +\dots + i \times k_i +\dots+(n-1) \times k_{n-1} \equiv i(mod n)$.

Now, we merge items in $\Delta$ according to the degree of $\varepsilon$. Then, we have the following:

and

Therefore, determining the value of $b_i$ is equivalent to studying all possibility of $k_0, k_1, \dots, k_{n-1}$ satisfying Eq $(4.1)$. Now, we first claim the following:

Claim 1. $b_i = b_j$ when $i \ne 0$ and $j \ne 0$.

In fact, if $a_{k_0}a_{k_1}a_{k_2} \dots a_{k_{n-1}}$ with $0\leq k_s\leq n-1$ is one term in $b_i$, then

Since $(i, n) = 1$ and $(j, n) = 1$, there exists $1 \leq t \leq n-1$ such that $it \equiv j(mod n)$, then, $0 \times k_0 \times t + 1 \times k_1 \times t +\dots+i \times k_i \times t +\dots+(n-1) \times k_{n-1} \times t \equiv it \equiv j(mod n)$,

that is

It follows from $1 \leq t \leq n-1$ that $(t, n) = 1$; therefore

Observing that $0 \times t, 1 \times t, 2 \times t, \dots, (n-1) \times t$ in the Eq (4.4) is just a reordering of $0, 1, 2, \dots, n-1$, we see that $a_{k_0}a_{k_1}a_{k_2} \dots a_{k_{n-1}}$ is also one term in $b_j$.

Conversely, it is also easy to see that every term $a_{k_0}a_{k_1}a_{k_2} \dots a_{k_{n-1}}$ with $0\leq k_s\leq n-1$ in $b_j$ is a one term in $b_i$. Thus, claim 1 is true.

Next, we claim the following:

Claim 2. $\Delta = b_0-b_1.$

In fact, by Claim 1, we have $b_1\varepsilon+ \cdots +b_i\varepsilon^i+ \cdots +b_{n-1}\varepsilon^{n-1} = b_1(\varepsilon+ \cdots +\varepsilon^i+ \cdots +\varepsilon^{n-1})$. Noticing that $1, \varepsilon, \cdots, \varepsilon^i, \cdots, \varepsilon^{n-1}$ are all roots of $x^n = 1$, we see that $\varepsilon+ \cdots +\varepsilon^i+ \cdots +\varepsilon^{n-1} = -1$ by the relationship between roots and coefficients, therefore, $\Delta = b_0-b_1.$

Now, we consider the computation of $b_0$ and $b_1$. By Eqs (4.1) and (4.3), we need to find all possible values ${k_0, k_1, \dots, k_{n-1}}$ such that $i = 0$ or $i = 1$ in (4.1). Noticing that $k_j$ is considered in the case of module $n$, we may assume $k_j\in Z_n = Z/\langle n\rangle$ for $0\leq j\leq n-1$. Based on the above discussion, if ${k_0, k_1, \dots, k_{n-1}}$ satisfy (4.1) for $i = 0$ or $i = 1$, then ${k_0, k_1, \dots, k_{n-1}}$ must be a solution of the following systems of linear equations (4.5) for $i = 0$ or (F) for $i = 1$:

or

Conversely, every solution ${k_0, k_1, \dots, k_{n-1}}$ of the systems (4.5) and (4.6) must satisfy (4.1) for either $i = 0$ or $i = 1$. Therefore, we should find all solutions of (4.5) and (4.6).

It is clear that (modulo $n$)

is a basic solution system of the systems of linear equation (4.5). Thus, the general solution of (4.5) is as follows:

where $c_0, c_2, \cdots, c_{n-1}$ in $Z_n$ are arbitrary.

It is also easy to see that

is a solution of the systems of linear equation (4.6). Thus, the general solution of the systems of linear equation (4.6) is as follows:

where $c_0, c_2, \cdots, c_{n-1}$ in $Z_n$ are arbitrary.

Hence

and

where ${c_0, c_2, \dots, c_{i}, \dots, c_{n-1}}$ satisfies $0 \leq c_r \leq n-1$ for $r \in \left\{0, 2, \dots, n-1\right\}$.

For convenience, let $\Phi = [(n-2)c_2+(n-3)c_3+\dots+c_{n-1}](mod n)$. Then,

Now, we can state the following results.

Theorem 4.1. Let $a_0, a_1, \cdots, a_{n-1}$ be real nubers and let $A = Circ(a_0, a_1, \cdots, a_{n-1})$ be the corresponding circulant matrix with a prime $n$. If $\Delta$ is the determinant of $A$, then

where ${c_0, c_2, \dots, c_{n-1}}$ satisfy $0 \leq c_r \leq n-1$ for $r \in \left\{0, 2, \dots, n-1\right\}$ and $\Phi = [(n-2)c_2+(n-3)c_3+\dots+c_{n-1}](mod n)$.

Since a matrix $A$ is invertible if and only if its determinant $|A|\neq 0$, Theorem 4.1 can provide a necessary and sufficient condition for the invertibility of circulant matrices with a prime order.

5.   Examples

In this section, we provide two examples to explain how to use the obtained results to calculate the determinant of a circulant matrix.

Example 5.1. Let $A_1 = Circ(0, 1, 2, 3, 4, 5, 6)$. Then, by Theorem 3.1, $A_1$ is invertible. Since the arrangement of $A_1$ is simple, it is easy to calculate the determinant of $A_1$ by using the properties of the determinant. On the other hand, we can use Theorem 4.1 to calculate the determinant of $A_1$ by Matlab, where $|A_1| = 352947$. The actual implementation (code) can be found in Figure 1.

Example 5.2. Let $A_2 = Circ(0, 1, 3, 4, 6, 8, 9)$. Then, by Theorem 3.1, $A_2$ is invertible. By Theorem 4.1, we can calculate the determinant of $A_2$ by Matlab, where $|A_2| = 5843624$. The actual implementation (code) can be found in Figure 1.

Remark 5.3. Theorem 4.1 greatly simplifies the calculation of the determinant of a circulant matrix with a prime order. For example, let $f_1(x) = x+2x^2+3x^3+4x^4+5x^5+6x^6$ and $f_2(x) = x+3x^2+4x^3+6x^4+8x^5+9x^6$. By Lemma 2.1, $|A_1| = \Pi ^{6}_{j = 0} f_1(\varepsilon ^j)$ and $|A_2| = \Pi ^{6}_{j = 0} f_2(\varepsilon ^j)$, where $\varepsilon$ is a primitive $7$-th root of unity, and $A_1$ and $A_2$ are exactly $A_1$ in Example 5.1 and $A_2$ in Example 5.2. If we calculate $\Pi ^{6}_{j = 0} f_1(\varepsilon ^j)$ and $\Pi ^{6}_{j = 0} f_2(\varepsilon ^j)$ by Matlab, the required calculation times are 0.3688 seconds and 0.2488 seconds, respectively (see Figure 2), and the required number of calculations is $7^8+7\times 28$ times. However, if we calculate $|A_1|$ and $|A_2|$ by Matlab (using Theorem 4.1), then the required calculation times are 0.0858 seconds and 0.0325 seconds, respectively (see Figure 1), and the required number of calculations is $7^6\times 18$ times.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the referees for their valuable suggestions and useful comments contributed to the final version of this paper. The authors also would like to express gratitude to Professor Wanzhou Ye and Professor Pengfei Bai for their assistance in preparing the manuscript. The first author was supported by the National Natural Science Foundation of China (12171302).

Conflict of interest

The authors declare there is no conflicts of interest.