Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Circulant matrix
open-in-new
<h2 id="definition">Definition</h2> <p>An n × n {\displaystyle n\times n} circulant matrix C {\displaystyle C} takes the form C = [ c 0 c n − 1 ⋯ c 2 c 1 c 1 c 0 c n − 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c n − 2 ⋱ ⋱ c n − 1 c n − 1 c n − 2 ⋯ c 1 c 0 ] {\displaystyle C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{n-1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-2}&&\ddots &\ddots &c_{n-1}\\c_{n-1}&c_{n-2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}} or the <a href="/facts/Transpose/8wmsagGS">transpose</a> of this form (by choice of notation). If each c i {\displaystyle c_{i}} is a p × p {\displaystyle p\times p} square <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a>, then the n p × n p {\displaystyle np\times np} matrix C {\displaystyle C} is called a block-circulant matrix. </p><p>A circulant matrix is fully specified by one vector, c {\displaystyle c} , which appears as the first column (or row) of C {\displaystyle C} . The remaining columns (and rows, resp.) of C {\displaystyle C} are each <a href="/facts/Cyclic_permutation/UndoYWpl">cyclic permutations</a> of the vector c {\displaystyle c} with offset equal to the column (or row, resp.) index, if lines are indexed from 0 {\displaystyle 0} to n − 1 {\displaystyle n-1} . (Cyclic permutation of rows has the same effect as cyclic permutation of columns.) The last row of C {\displaystyle C} is the vector c {\displaystyle c} shifted by one in reverse. </p><p>Different sources define the circulant matrix in different ways, for example as above, or with the vector c {\displaystyle c} corresponding to the first row rather than the first column of the matrix; and possibly with a different direction of shift (which is sometimes called an anti-circulant matrix). </p><p>The <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> f ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 {\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}} is called the <i>associated polynomial</i> of the matrix C {\displaystyle C} . </p> <h2 id="properties">Properties</h2> <h3>Eigenvectors and eigenvalues</h3> <p>The normalized <a href="/facts/Eigenvector/8TjEoT8u">eigenvectors</a> of a circulant matrix are the Fourier modes, namely, v j = 1 n ( 1 , ω j , ω 2 j , … , ω ( n − 1 ) j ) T , j = 0 , 1 , … , n − 1 , {\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right)^{T},\quad j=0,1,\ldots ,n-1,} where ω = exp ( 2 π i n ) {\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)} is a primitive n {\displaystyle n} -th <a href="/facts/Root_of_unity/EqH0ho1Y">root of unity</a> and i {\displaystyle i} is the <a href="/facts/Imaginary_unit/1SCllQlU">imaginary unit</a>. </p><p>(This can be understood by realizing that multiplication with a circulant matrix implements a convolution. In Fourier space, convolutions become multiplication. Hence the product of a circulant matrix with a Fourier mode yields a multiple of that Fourier mode, i.e. it is an eigenvector.) </p><p>The corresponding <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalues</a> are given by λ j = c 0 + c 1 ω − j + c 2 ω − 2 j + ⋯ + c n − 1 ω − ( n − 1 ) j , j = 0 , 1 , … , n − 1. {\displaystyle \lambda _{j}=c_{0}+c_{1}\omega ^{-j}+c_{2}\omega ^{-2j}+\dots +c_{n-1}\omega ^{-(n-1)j},\quad j=0,1,\dots ,n-1.} </p> <h3>Determinant</h3> <p>As a consequence of the explicit formula for the eigenvalues above, the <a href="/facts/Determinant/eGYqJ2TF">determinant</a> of a circulant matrix can be computed as: det C = ∏ j = 0 n − 1 ( c 0 + c n − 1 ω j + c n − 2 ω 2 j + ⋯ + c 1 ω ( n − 1 ) j ) . {\displaystyle \det C=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j}).} Since taking the transpose does not change the eigenvalues of a matrix, an equivalent formulation is det C = ∏ j = 0 n − 1 ( c 0 + c 1 ω j + c 2 ω 2 j + ⋯ + c n − 1 ω ( n − 1 ) j ) = ∏ j = 0 n − 1 f ( ω j ) . {\displaystyle \det C=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j})=\prod _{j=0}^{n-1}f(\omega ^{j}).} </p> <h3>Rank</h3> <p>The <a href="/facts/Rank_(linear_algebra)/Yp9b5LK3">rank</a> of a circulant matrix C {\displaystyle C} is equal to n − d {\displaystyle n-d} where d {\displaystyle d} is the <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree</a> of the polynomial gcd ( f ( x ) , x n − 1 ) {\displaystyle \gcd(f(x),x^{n}-1)} .<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h3>Other properties</h3> <ul><li>Any circulant is a matrix polynomial (namely, the associated polynomial) in the cyclic <a href="/facts/Permutation_matrix/xC1ran5s">permutation matrix</a> P {\displaystyle P} : C = c 0 I + c 1 P + c 2 P 2 + ⋯ + c n − 1 P n − 1 = f ( P ) , {\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),} where P {\displaystyle P} is given by the <a href="/facts/Companion_matrix/IHCGAdPr">companion matrix</a> P = [ 0 0 ⋯ 0 1 1 0 ⋯ 0 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 0 0 ⋯ 0 1 0 ] . {\displaystyle P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.} </li> <li>The <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of n × n {\displaystyle n\times n} circulant matrices forms an n {\displaystyle n} -<a href="/facts/Dimension_(vector_space)/z8m02A3W">dimensional</a> <a href="/facts/Vector_space/M1pxMLx2">vector space</a> with respect to addition and scalar multiplication. This space can be interpreted as the space of <a href="/facts/Function_(mathematics)/CdReEKCh">functions</a> on the <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> of <a href="/facts/Order_of_a_group/Cl3tKGFg">order</a> n {\displaystyle n} , C n {\displaystyle C_{n}} , or equivalently as the <a href="/facts/Group_ring/TJlkt5Te">group ring</a> of C n {\displaystyle C_{n}} .</li> <li>Circulant matrices form a <a href="/facts/Commutative_algebra_(structure)/DRfoF6KV">commutative algebra</a>, since for any two given circulant matrices A {\displaystyle A} and B {\displaystyle B} , the sum A + B {\displaystyle A+B} is circulant, the product A B {\displaystyle AB} is circulant, and A B = B A {\displaystyle AB=BA} .</li> <li>For a <a href="/facts/Nonsingular_matrix/fPqXk3V8">nonsingular</a> circulant matrix A {\displaystyle A} , its <a href="/facts/Inverse_matrix/fPqXk3V8">inverse</a> A − 1 {\displaystyle A^{-1}} is also circulant. For a singular circulant matrix, its <a href="/facts/Moore%25E2%2580%2593Penrose_inverse/CU73tntq">Moore–Penrose pseudoinverse</a> A + {\displaystyle A^{+}} is circulant.</li> <li>The <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> matrix of order n {\displaystyle n} is defined as by</li></ul> <p> F n = ( f j k ) with f j k = e − 2 π i / n ⋅ j k , for 0 ≤ j , k ≤ n − 1. {\displaystyle F_{n}=(f_{jk}){\text{ with }}f_{jk}=e^{-2\pi i/n\cdot jk},\,{\text{for }}0\leq j,k\leq n-1.} There are important connections between circulant matrices and the DFT matrices. In fact, it can be shown that C = F n − 1 diag ( F n c ) F n , {\displaystyle C=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},} where c {\displaystyle c} is the first column of C {\displaystyle C} . The eigenvalues of C {\displaystyle C} are given by the product F n c {\displaystyle F_{n}c} . This product can be readily calculated by a <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <ul><li>Let p ( x ) {\displaystyle p(x)} be the (<a href="/facts/Monic_polynomial/4JzuIJ5R">monic</a>) <a href="/facts/Characteristic_polynomial/7m8roDqo">characteristic polynomial</a> of an n × n {\displaystyle n\times n} circulant matrix C {\displaystyle C} . Then the scaled <a href="/facts/Derivative/7Ito70Dh">derivative</a> 1 n p ′ ( x ) {\textstyle {\frac {1}{n}}p'(x)} is the characteristic polynomial of the following ( n − 1 ) × ( n − 1 ) {\displaystyle (n-1)\times (n-1)} submatrix of C {\displaystyle C} : C n − 1 = [ c 0 c n − 1 ⋯ c 3 c 2 c 1 c 0 c n − 1 c 3 ⋮ c 1 c 0 ⋱ ⋮ c n − 3 ⋱ ⋱ c n − 1 c n − 2 c n − 3 ⋯ c 1 c 0 ] {\displaystyle C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}} (see <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> for the <a href="/facts/Mathematical_proof/7ECDrU80">proof</a>).</li></ul> <h2 id="analytic-interpretation">Analytic interpretation</h2> <p>Circulant matrices can be interpreted <a href="/facts/Geometry/wTQf5ffQ">geometrically</a>, which explains the connection with the discrete Fourier transform. </p><p>Consider vectors in R n {\displaystyle \mathbb {R} ^{n}} as functions on the <a href="/facts/Integer/PUwwrawx">integers</a> with period n {\displaystyle n} , (i.e., as periodic bi-infinite sequences: … , a 0 , a 1 , … , a n − 1 , a 0 , a 1 , … {\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots } ) or equivalently, as functions on the <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> of order n {\displaystyle n} (denoted C n {\displaystyle C_{n}} or Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } ) geometrically, on (the vertices of) the <a href="/facts/Regular_polygon/ws89Nhpt">regular n {\displaystyle n} -gon</a>: this is a discrete analog to periodic functions on the <a href="/facts/Real_line/6eq42xX5">real line</a> or <a href="/facts/Circle/9fy5ggKn">circle</a>. </p><p>Then, from the perspective of <a href="/facts/Operator_theory/Ays1ofel">operator theory</a>, a circulant matrix is the kernel of a discrete <a href="/facts/Integral_transform/AB2yjHJJ">integral transform</a>, namely the <a href="/facts/Convolution_operator/PVPrdz9J">convolution operator</a> for the function ( c 0 , c 1 , … , c n − 1 ) {\displaystyle (c_{0},c_{1},\dots ,c_{n-1})} ; this is a discrete <a href="/facts/Circular_convolution/krbXy3LH">circular convolution</a>. The formula for the convolution of the functions ( b i ) := ( c i ) ∗ ( a i ) {\displaystyle (b_{i}):=(c_{i})*(a_{i})} is </p> b k = ∑ i = 0 n − 1 a i c k − i {\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}} <p>(recall that the sequences are periodic) which is the product of the vector ( a i ) {\displaystyle (a_{i})} by the circulant matrix for ( c i ) {\displaystyle (c_{i})} . </p><p>The discrete Fourier transform then converts convolution into multiplication, which in the matrix setting corresponds to diagonalization. </p><p>The C ∗ {\displaystyle C^{*}} -algebra of all circulant matrices with <a href="/facts/Complex_number/2w7mqI7e">complex</a> entries is <a href="/facts/Isomorphic/pj8KgkxU">isomorphic</a> to the group C ∗ {\displaystyle C^{*}} -algebra of Z / n Z . {\displaystyle \mathbb {Z} /n\mathbb {Z} .} </p> <h2 id="symmetric-circulant-matrices">Symmetric circulant matrices</h2> <p>For a <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric</a> circulant matrix C {\displaystyle C} one has the extra condition that c n − i = c i {\displaystyle c_{n-i}=c_{i}} . Thus it is determined by ⌊ n / 2 ⌋ + 1 {\displaystyle \lfloor n/2\rfloor +1} elements. C = [ c 0 c 1 ⋯ c 2 c 1 c 1 c 0 c 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c 2 ⋱ ⋱ c 1 c 1 c 2 ⋯ c 1 c 0 ] . {\displaystyle C={\begin{bmatrix}c_{0}&c_{1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}.} </p><p>The eigenvalues of any <a href="/facts/Real_number/R02gw5Pb">real</a> symmetric matrix are real. The corresponding eigenvalues λ → = n ⋅ F n † c {\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c} become: λ k = c 0 + c n / 2 e − π i ⋅ k + 2 ∑ j = 1 n 2 − 1 c j cos ( − 2 π n ⋅ k j ) = c 0 + c n / 2 ω k n / 2 + 2 c 1 ℜ ω k + 2 c 2 ℜ ω k 2 + ⋯ + 2 c n / 2 − 1 ℜ ω k n / 2 − 1 {\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}} for n {\displaystyle n} <a href="/facts/Parity_(mathematics)/7zq2UM4V">even</a>, and λ k = c 0 + 2 ∑ j = 1 n − 1 2 c j cos ( − 2 π n ⋅ k j ) = c 0 + 2 c 1 ℜ ω k + 2 c 2 ℜ ω k 2 + ⋯ + 2 c ( n − 1 ) / 2 ℜ ω k ( n − 1 ) / 2 {\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}} for n {\displaystyle n} <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a>, where ℜ z {\displaystyle \Re z} denotes the <a href="/facts/Complex_number/2w7mqI7e">real part</a> of z {\displaystyle z} . This can be further simplified by using the fact that ℜ ω k j = ℜ e − 2 π i n ⋅ k j = cos ( − 2 π n ⋅ k j ) {\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)} and ω k n / 2 = e − 2 π i n ⋅ k n 2 = e − π i ⋅ k {\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}} depending on k {\displaystyle k} even or odd. </p><p>Symmetric circulant matrices belong to the class of <a href="/facts/Bisymmetric_matrix/oKXyA2lz">bisymmetric matrices</a>. </p> <h2 id="hermitian-circulant-matrices">Hermitian circulant matrices</h2> <p>The complex version of the circulant matrix, ubiquitous in communications theory, is usually <a href="/facts/Hermitian_matrix/qArPblYo">Hermitian</a>. In this case c n − i = c i ∗ , i ≤ n / 2 {\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2} and its determinant and all eigenvalues are real. </p><p>If <i>n</i> is even the first two rows necessarily takes the form [ r 0 z 1 z 2 r 3 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 r 3 z 2 ∗ … ] . {\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}\\\dots \\\end{bmatrix}}.} in which the first element r 3 {\displaystyle r_{3}} in the top second half-row is real. </p><p>If <i>n</i> is odd we get [ r 0 z 1 z 2 z 2 ∗ z 1 ∗ z 1 ∗ r 0 z 1 z 2 z 2 ∗ … ] . {\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.} </p><p>Tee<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> has discussed constraints on the eigenvalues for the Hermitian condition. </p> <h2 id="applications">Applications</h2> <h3>In linear equations</h3> <p>Given a matrix equation </p> C x = b , {\displaystyle C\mathbf {x} =\mathbf {b} ,} <p>where C {\displaystyle C} is a circulant matrix of size n {\displaystyle n} , we can write the equation as the <a href="/facts/Circular_convolution/krbXy3LH">circular convolution</a> c ⋆ x = b , {\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,} where c {\displaystyle \mathbf {c} } is the first column of C {\displaystyle C} , and the vectors c {\displaystyle \mathbf {c} } , x {\displaystyle \mathbf {x} } and b {\displaystyle \mathbf {b} } are cyclically extended in each direction. Using the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">circular convolution theorem</a>, we can use the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> to transform the cyclic convolution into component-wise multiplication F n ( c ⋆ x ) = F n ( c ) F n ( x ) = F n ( b ) {\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )} so that x = F n − 1 [ ( ( F n ( b ) ) ν ( F n ( c ) ) ν ) ν ∈ Z ] T . {\displaystyle \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\!\nu \in \mathbb {Z} }\,\right]^{\rm {T}}.} </p><p>This algorithm is much faster than the standard <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>, especially if a <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> is used. </p> <h3>In graph theory</h3> <p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> or <a href="/facts/Directed_graph/YBdfQ0um">digraph</a> whose <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> is circulant is called a <a href="/facts/Circulant_graph/b51YF380">circulant graph</a>/digraph. Equivalently, a graph is circulant if its <a href="/facts/Automorphism_group/65vImKwe">automorphism group</a> contains a full-length cycle. The <a href="/facts/M%25C3%25B6bius_ladder/J6xLNMz0">Möbius ladders</a> are examples of circulant graphs, as are the <a href="/facts/Paley_graph/SHbT4vj5">Paley graphs</a> for <a href="/facts/Field_(mathematics)/xAjAS4ko">fields</a> of <a href="/facts/Prime_number/L20FLkgn">prime</a> order. </p> <h2 id="external-links">External links</h2> <ul><li>Gray, R.M. (2006). <a href="http://www-ee.stanford.edu/~gray/toeplitz.pdf"><i>Toeplitz and Circulant Matrices: A Review</i></a> (PDF). Foundations and Trends in Communications and Information Theory. Vol. 2. Now. pp. 155–239. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1561%2F0100000006">10.1561/0100000006</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-933019-68-0 – via Stanford University.</li> <li><a href="https://github.com/MMesch/toeplitz_spectrum/blob/master/toeplitz_spectrum.ipynb">IPython Notebook demonstrating properties of circulant matrices</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Davis, Philip J (1970). Circulant Matrices. New York: Wiley. ISBN 0-471-05771-1. OCLC 1408988930. <a href="0-471-05771-1" target="_blank">0-471-05771-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>A. W. Ingleton (1956). "The Rank of Circulant Matrices". J. London Math. Soc. s1-31 (4): 445–460. doi:10.1112/jlms/s1-31.4.445. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Golub, Gene H.; Van Loan, Charles F. (1996), "§4.7.7 Circulant Systems", Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9 <a href="978-0-8018-5414-9" target="_blank">978-0-8018-5414-9</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Kushel, Olga; Tyaglov, Mikhail (July 15, 2016), "Circulants and critical points of polynomials", Journal of Mathematical Analysis and Applications, 439 (2): 634–650, arXiv:1512.07983, doi:10.1016/j.jmaa.2016.03.005, ISSN 0022-247X <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Tee, G.J. (2007). "Eigenvectors of Block Circulant and Alternating Circulant Matrices" (PDF). New Zealand Journal of Mathematics. 36: 195–211. <a href="https://core.ac.uk/download/pdf/148639176.pdf" target="_blank">https://core.ac.uk/download/pdf/148639176.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> </ol>