{"id":232,"date":"2024-08-25T21:18:12","date_gmt":"2024-08-25T13:18:12","guid":{"rendered":"https:\/\/www.shirui.me\/blog\/?p=232"},"modified":"2024-08-25T21:18:12","modified_gmt":"2024-08-25T13:18:12","slug":"eigenvalues-of-circulant-matrices","status":"publish","type":"post","link":"https:\/\/www.shirui.me\/blog\/2024\/08\/25\/eigenvalues-of-circulant-matrices\/","title":{"rendered":"Eigenvalues of circulant matrices"},"content":{"rendered":"\n

A circulant matrix is defined as:<\/p>\n

$C=\\begin{bmatrix}c_{0}&c_{n-1}&\\dots &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}&\\dots &c_{1}&c_{0}\\\\\\end{bmatrix}$<\/p>\n

where $C_{j, k}=c_{j-k \\mod n}$. The $k$-th eigenvalue $\\lambda_k$ and eigenvector $x_k$ satisfy $C\\cdot x_k=\\lambda_k x_k$, which can be expressed as $n$ equations:<\/p>\n

$\\sum_{j=0}^{m-1}c_{m-j}x_j+\\sum_{j=m}^{n-1}c_{n-j+m}x_j=\\lambda_k x_m\\quad m=0,1,\\dots,n-1$<\/p>\n

with $c_n=c_0$, where $x_m$ is the $m$-th component of the eigenvector $x_k$. By changing the dummy summing variables ($j\\to m-j$ and $j\\to n-j+m$), we obtain:<\/p>\n

$\\sum_{j=1}^{m}c_j x_{m-j} +\\sum_{j=m+1}^{n}c_j x_{n+m-j}=\\lambda_k x_m$<\/p>\n

with $m=0,1,2,\\dots,n-1$. We can “guess” a solution where $x_j=\\omega^j$, which transforms the equation into:<\/p>\n

$\\begin{align}&\\sum_{j=1}^{m}c_j \\omega^{m-j} +\\sum_{j=m+1}^{n}c_j \\omega^{n+m-j}=\\lambda_k \\omega^m\\\\ \\leftrightarrow &\\sum_{j=1}^{m}c_j \\omega^{-j} +\\omega^{n}\\sum_{j=m+1}^{n}c_j \\omega^{-j}=\\lambda_k\\end{align}$<\/p>\n

Let $\\omega$ be one of the $n$-th roots of unity, i.e., $\\omega = \\exp(-2\\pi\\mathbb{i}\/n)$, then $\\omega^{n}=1$. This leads to the eigenvalue:<\/p>\n

$\\lambda = \\sum_{j=0}^{n-1}\\omega^{-j} c_j$<\/p>\n

with the corresponding eigenvector:<\/p>\n

$x= (1, \\exp(2\\pi\\mathbb{i}\/n), \\exp(2\\pi\\mathbb{i}\/n)^2,\\dots,\\exp(2\\pi\\mathbb{i}\/n)^{n-1})^T$<\/p>\n

The $k$-th eigenvalue is generated from $\\omega^{-k} = \\exp(2\\pi k\\mathbb{i}\/n)$ with $k\\in [0,n-1]$, resulting in the $k$-th eigenvalue and eigenvector:<\/p>\n

$\\lambda_k = \\sum_{j=0}^{n-1}c_j \\exp(2\\pi k\\mathbb{i}\/n)$<\/p>\n

and<\/p>\n

$x_k = (1, \\exp(2\\pi k\\mathbb{i}\/n), \\exp(2\\pi k\\mathbb{i}\/n)^2,\\dots,\\exp(2\\pi k\\mathbb{i}\/n)^{n-1})^T$<\/p>\n

The eigenspace is simply the DFT matrix, and all circulant matrices share the same eigenspace. It is easy to verify that circulant matrices possess the following properties:<\/p>\n

If $A$ and $B$ are circulant matrices, then:<\/p>\n

    \n
  1. $AB=BA=W^\\ast\\Gamma W$ where $W$ is the DFT matrix and $\\Gamma=\\Gamma_A\\Gamma_B$, with $\\Gamma_i$ representing the diagonal matrix consisting of the eigenvalues of $i$; $\\Gamma_A = WAW^\\ast$.<\/li>\n
  2. $B+A=A+B=W^\\ast\\Omega W$, where $\\Omega=\\Gamma_A+\\Gamma_B$.<\/li>\n
  3. If $\\mathrm{det}(A)\\ne 0$, then $A^{-1}=W^\\ast \\Gamma_A^{-1}W$.<\/li>\n<\/ol>\n

    The proof is straightforward:<\/p>\n

      \n
    1. $AB=W^\\ast \\Gamma_AW W^\\ast\\Gamma_BW=$
      $W^\\ast\\Gamma_A\\Gamma_BW=W^\\ast \\Gamma_B\\Gamma_AW=BA$<\/li>\n
    2. $W(A+B)W^\\ast=\\Gamma_A+\\Gamma_B$.<\/li>\n
    3. $AW^\\ast \\Gamma_A^{-1}W=W^\\ast \\Gamma_AW W^\\ast \\Gamma_A^{-1}W=\\mathbb{I}$<\/li>\n<\/ol>\n\n","protected":false},"excerpt":{"rendered":"

      A circulant matrix is defined as: $C=\\begin{bmatrix}c_{0}&c_{n-1}&\\dots &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}&\\dots &c_{1}&c_{0}\\\\\\end{bmatrix}$ where $C_{j, k}=c_{j-k \\mod n}$. The $k$-th eigenvalue $\\lambda_k$ and eigenvector $x_k$ satisfy $C\\cdot x_k=\\lambda_k x_k$, which can be expressed as $n$ equations: $\\sum_{j=0}^{m-1}c_{m-j}x_j+\\sum_{j=m}^{n-1}c_{n-j+m}x_j=\\lambda_k x_m\\quad m=0,1,\\dots,n-1$ with $c_n=c_0$, where $x_m$ is the $m$-th component of the eigenvector $x_k$. By changing the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[30],"class_list":["post-232","post","type-post","status-publish","format-standard","hentry","category-notes","tag-simple-math"],"_links":{"self":[{"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/posts\/232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/comments?post=232"}],"version-history":[{"count":1,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/posts\/232\/revisions"}],"predecessor-version":[{"id":233,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/posts\/232\/revisions\/233"}],"wp:attachment":[{"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/media?parent=232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/categories?post=232"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shirui.me\/blog\/wp-json\/wp\/v2\/tags?post=232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}