Skip to main content

Questions tagged [circulant-matrices]

For questions regarding circulant matrices, where each row vector is rotated one element to the right relative to the preceding row vector.

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

Circulant determinant of even size - missing term

Circulant matrix of size $n$ over any commutative ring $\textbf{R}$ is following square matrix $$ \mathscr{C}(c_1, c_2, c_3, \dots, c_{n-1}, c_n):= \begin{pmatrix} c_1 & c_2 & c_3 & \...
Oliver Bukovianský's user avatar
1 vote
1 answer
56 views

Eigenstructure of (Symmetric Block-Circulant) Covariance Matrix from Modular Arithmetic

I'm trying to understand the eigenvalues of a particular block-circulant matrix $\Sigma$. I'm studying modular arithmetic, specifically $x + y \pmod p$. I call $p$ the "modulus" or the "...
Rylan Schaeffer's user avatar
3 votes
2 answers
277 views

Is Johnson Graph J(N, 2) circulant?

I have stumbled upon the problem of diagonalizing the matrix of a Johnson graph $(N,k)$ with $k=2$. From Wikipedia and several other references I found the explicit form for the eigenvalues https://en....
Alessio Catanzaro's user avatar
0 votes
0 answers
72 views

Eigenvalues of Circulant Matrix Plus Diagonal Matrix

I am trying to find the eigenvalues of a real circulant matrix, $C$, plus a real diagonal matrix, $D$. My approach has been to successively apply the matrix determinant lemma by viewing $$D = \sum_{i=...
vlovero's user avatar
  • 87
2 votes
1 answer
153 views

How to compute the determinant of a block circulant matrix?

I am curious if there are any general formulas for problems like this or special cases. I want to compute the determinant of $2n \times 2n$ complex matrices made of identical $2 \times 2$ matrices. If ...
Thtm's user avatar
  • 31
1 vote
2 answers
100 views

Determinant of the circulant matrix corresponding to the $r$-tuple $(1, 1, 0, 0, \ldots , 0, 0)$

For any integer $r \geq 3$, consider the $r$-tuple $(1, 1, 0, 0, \ldots , 0, 0)$ (involving $r - 2$ zeros) which represents the first row of the corresponding $r \times r$ circulant matrix. Show that ...
Aleph-null's user avatar
1 vote
1 answer
52 views

Spectrum of circulant block matrix of circulant blocks (Adjacency matrix of discrete torus)

I am currently investigating the spectrum of a matrix $M \in \mathbb{R}^{12 \times 12}$. The matrix has the following form, $$ M = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 &...
SebastianP's user avatar
3 votes
2 answers
197 views

The inverse of the "Given vertices find area of polygon in complex plane" problem

Let $\omega_0, \ldots, \omega_{n-1}$ be the $n$-th roots of unity, and $a_0, \ldots, a_{n-1}$ be real numbers in the $(0, 1]$ interval. Define $z_i = a_i \omega_i$ as the vertices of a polygon on the ...
Andre Paulino de Lima's user avatar
0 votes
0 answers
43 views

Relation for maximum eigenvalue of 2-tridiagonal Toeplitz matrix

Let an 8x8 2-tridiagonal Toeplitz matrix is of the form S1. From the literature Eigenvalues of 2-tridiagonal Toeplitz matrix its easy to findout the maximum eigenvalue of S1. S1=$ \begin{bmatrix} a &...
Krishna's user avatar
  • 11
1 vote
0 answers
39 views

What is the correct terminology for this circulant & symmetric matrix with only two distinct elements?

Is there a special terminology to describe a matrix of the following form in $\mathbb{C}^{4\times 4}$ or more generally $\mathbb{C}^{N\times N}$? $\begin{bmatrix} a & b & b & b \\ b & ...
Mantabit's user avatar
  • 203
2 votes
1 answer
58 views

Are there real normal matrices with non-negative entries that are asymmetric and non-circulant?

Is there an example of a normal matrix with real non-negative entries that is neither symmetric nor circulant/block-circulant? If not, is there a proof of this property/reference to proof? ...
citizenfour's user avatar
5 votes
1 answer
143 views

Coefficients of a symmetric product of polynomials with root of unity

For number $n\ge2$, let $\xi$ be a primitive $n$-th root of unity. The determinant of circulant matrix is a symmetric polynomial in $x_0,\dots,x_{n-1}$ $$f_n=\prod_{j=0}^{n-1}\sum_{i=0}^{n-1}ξ^{ij}x_i$...
hbghlyj's user avatar
  • 3,047
0 votes
0 answers
71 views

Conditions for solving a Circulant-plus-diagonal system

Let $\matrix{C}$ be a $n \times n $ circulant matrix with generating vector $\vec{c} = \{0 , c_1, c_2, \cdots, c_k, 0,\cdots, 0\} $ where $k \le n-1$. Let $\matrix{A}$ be a diagonal matrix with ...
Andreas's user avatar
  • 15.8k
0 votes
1 answer
84 views

Prove that for every root of unity $z$ of size $n$, the vector ($1, z, z^2,..., z^{n-1}$) is an eigenvector of the circulant matrix $A$ [closed]

Let $a_1, a_2, \dots, a_n \in \Bbb{C}$. Let $$ A = \begin{bmatrix} a_1 & a_2 & \dots & a_{n-1} &a_n\\ a_n & a_1 & \dots & a_{n-2} & a_{n-1}\\ \vdots & \vdots & \...
NitaStack's user avatar
2 votes
0 answers
53 views

Solutions to diophantine equations involving the determinant of circulant matrices

let $A$ be a circulant matrix over the integers, i was wondering if anyone knew of resources discussing the diophantine equation $\det(A) = 1$. So in the case of the circulant matrix being a $3 \times ...
eagle I 's user avatar
0 votes
0 answers
76 views

Fast matrix multiplication with one symmetric circulant matrix

I have a symmetric circulant matrix $C \in \mathbb{R}^{n\times n}$, a sparse matrix $G \in \mathbb{R}^{m\times n}$, and a vector $x \in \mathbb{R}^{2m\times 1}$. I need to find the most numerically ...
Matthew James's user avatar
1 vote
0 answers
114 views

Quadratic optimization with FFT

I'm trying to solve the following bounded quadratic optimization problem. \begin{equation} \min_{x} \frac{1}{2}x^TAx+b^Tx \end{equation} \begin{equation} \textrm{s.t. }\\ x \geq 0 \end{equation} Where ...
Matthew James's user avatar
1 vote
3 answers
269 views

Quadratic matrix equation $X X' = A$

Find $n\,\,0-1$ matrices $Y_i, i = 1,\dots,n$ with $n$ rows and $n^2$ columns such that: $Y_iY_j' = \mathbf{1}_n, \forall i\ne j$ $Y_iY_i' = nI_n$ We can write this matrix equations as a single block ...
koko's user avatar
  • 69
0 votes
0 answers
104 views

How to decompose a matrix into a sum of circulant matrices

I have a very particular matrix $A = \alpha e_1 e_1^T$, where $\alpha$ is constant, means it has only one element in the diagonal that is different from zero. Can this matrix be decomposed into a ...
user3284182's user avatar
2 votes
0 answers
62 views

Eigenvalues of quasi circulant matrix

I have to find the eigenvalues of a quasi-circulant matrix. I found this answer here: Eigenvalues and eigenvectors for a quasi-circulant matrix But I cannot understand what is $nt$ and how the guy ...
user3284182's user avatar
0 votes
1 answer
153 views

Diagonalization of a combination of circulant matrices

Write \begin{align} A &= \sum_{k=1}^r C_k E_k \in \mathbb{R}^{n \times n} \end{align} where $C_k$ are diagonal matrices and $E_k$ are circulant matrices for all $k \in \{1,2,\dots,r\}$. Given $x \...
mlbj's user avatar
  • 129
0 votes
0 answers
26 views

$2$-norm of a matrix obtained through discretization of the eigenvalue problem

Define $$A = \frac{1}{2h} \begin{pmatrix} 0 & 1 & & & & -1\\ -1 & 0 & 1 & & \\ &\ddots & \ddots & \ddots \\ & & & -1 & 0 & 1 \\ 1 &...
Sam's user avatar
  • 3,360
1 vote
0 answers
58 views

Eigenvalues of a circulant matrix with an updated term

$$ \begin{Bmatrix} a & b & 0 &\dots & 0 & c \\ c & 0 & b &\dots & 0 & 0 \\ 0 & c & \ddots &\ddots & 0 & 0 \\ \vdots &...
Mhetre's user avatar
  • 19
8 votes
3 answers
272 views

Find the $n$th power of a 3-by-3 circulant matrix

Consider the matrix given as $$A=\begin{bmatrix}a_0 & a_2 & a_1\\ a_1 & a_0 & a_2\\ a_2 & a_1 & a_0\end{bmatrix}$$ Write a formula for $A^n$ for $n\in\mathbb{N}$. $$$$ My ...
mrx king's user avatar
  • 161
5 votes
0 answers
120 views

Circulant determinant factorization over Z

Let $X_n= \begin{bmatrix} x_1&x_2&\cdots&x_n\\ x_n&x_1&\cdots&x_{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ x_2&x_3&\cdots&x_1\\ \end{bmatrix} $ be a ...
Tomm's user avatar
  • 71
3 votes
1 answer
160 views

Generating doubly block circulant matrices which are also symmetric positive definite

I have generated in python some matrices with doubly block circulant structure (i.e. also the blocks themselves are circulant). These matrices are square, sparse and with coefficient drawn from ...
Betelgeuse's user avatar
1 vote
0 answers
57 views

Can an arbitrary diagonal matrix be used to generate a 3 level circulant matrix?

From here, we know the BCCB (block circulant with circulant blocks, a 2 level circulant matrix) can be diagonalized by the Fourier basis. The references therein actually tell us this is true in ...
Physics Enthusiast's user avatar
0 votes
0 answers
100 views

On the eigenvectors of a circulant matrix

A circulant matrix is a square matrix whose each row is the preceding row rotated to the right by one element, e.g., the following is a $3 \times 3$ circulant matrix. $$\begin{bmatrix} 1 & 2 & ...
Tapi's user avatar
  • 1,686
0 votes
0 answers
99 views

Compute the singular values of convolution matrix through fast Fourier transform

Given any vector $\boldsymbol{x}=(x_1,x_2,\ldots,x_n)^\top\in\mathbb{R}^{n}$ with a certain kernel size $\tau\in\mathbb{N}^+$ ($1<\tau<n$), then its convolution matrix is given by \begin{...
Xinyu Chen's user avatar
1 vote
1 answer
152 views

Nuclear norm minimization of a circulant matrix with fast Fourier transform

Given any vector $\boldsymbol{x}=(x_1,x_2,\cdots,x_n)^\top\in\mathbb{R}^{n}$, its circulant matrix can be written as follows, \begin{equation} \mathcal{C}(\boldsymbol{x})=\begin{bmatrix}x_1 & x_n &...
Xinyu Chen's user avatar
1 vote
0 answers
23 views

Are there any normal and Toeplitz matrices which are not circulant?

The way I understand it currently, an Euler diagram can be made of normal, circulant, and Toeplitz matrices which looks like this: My question: is $\left( \text{Normal} \, \cap \, \text{Toeplitz} \...
Ptch's user avatar
  • 11
1 vote
1 answer
153 views

Circulant-like determinant

Let $a_0, a_1, a_2, \dots, a_n \in \mathbb{C}$. How can I compute the following determinant? $$\begin{vmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ -a_{n-1} & a_0 & a_1 & \...
MathLearner's user avatar
  • 1,021
2 votes
1 answer
318 views

Eigenvalues for discrete second derivative with periodic boundary conditions

This wikipedia page https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors_of_the_second_derivative for the discrete second derivative ivative says that the eigenvalue problem $v_{k+1}-2v_k+v_{k-1}...
LaguerreGroup's user avatar
0 votes
0 answers
72 views

Diagonalizing a matrix that is close to a circulant one in symmetry

Recently encountered a matrix that looks similar to a circulant, and in case of a $5\times 5$ matrix, we have: $$ A = \begin{pmatrix} \omega^0 c_0 & \omega^1 c_1 & \omega^2 c_2 & \omega^3 ...
Sl0wp0k3's user avatar
  • 526
-1 votes
1 answer
195 views

Inverse circulant matrix is circulant [duplicate]

I am trying to proof that the inverse of a circulant matrix is also circulant and had figured the best way to do it would be using the diagonalisation: $$ \begin{align*} C^{-1} &= (\frac{1}{n} F_{...
ThatBoi's user avatar
  • 13
1 vote
1 answer
72 views

Can we say anything about the eigenvalues/eigenvectors of a matrix composed by submatrices in a 'circulant' way?

Circulant matrices, that is matrices in $\mathbb{R}^{n \times n}$ of the form $$\begin{pmatrix} c_0 & c_1 & c_2 & ... & c_n \\ c_n & c_0 & c_1 &... & c_{n-1} \\ c_{n-1} ...
a_student's user avatar
  • 1,504
1 vote
1 answer
63 views

Determinant of circulant $(0,1)$ matrices of certain form

I am interested in computing the determinant of the following circulant matrices: let $n=p^k$ for $p$ a prime and $k\in \mathbb{N}$, take $a\in \mathbb{N}$ to be such that $a<p$ and $(a,p)=1$. ...
Jones's user avatar
  • 277
0 votes
1 answer
52 views

Diagonalize matrix of linear operator

Let $f : \mathbb{C} \to \mathbb{C}$ linear map such $$ f(e_{i}) = \begin{cases} e_{i+1} & 1 \leq i<n \\ e_{1} & i=n\end{cases}$$ Diagonalize $f$. Thoughts I know the characteristic ...
G. Ticher's user avatar
  • 135
1 vote
1 answer
90 views

Operations with Circulant Matrix using GAP

I am newbie using GAP software. I need to know how to use GAP software for algebraic computations with circulant matrix. Some examples would suffice. Just for clarity Circulant Matrix: In linear ...
sujikin's user avatar
  • 119
2 votes
1 answer
188 views

Find general form of eigenvalues of a circulant matrix

I have an $n \times n$ matrix in a general form: $$ A = \begin{pmatrix} \alpha^{n-1} & 1 & \alpha & \alpha^2 & \dots & \alpha^{n-2} \\ \alpha^{n-2} & \alpha^{n-1} & 1 &...
Yauhen Yakimenka's user avatar
2 votes
3 answers
901 views

Solving linear system $Ax=b$ via FFT

On Wikipedia, I read that it is possible to solve $Ax=b$ when the matrix $A$ is circulant via the Fast Fourier Transform (FFT). For example, I have $$\begin{bmatrix} 1 & 0 & 0 & -1 \\ -1 &...
Blake's user avatar
  • 107
0 votes
0 answers
55 views

results of calculating eigenvalues and eigenvectors of permutation matrix

My question is actually about the derivation of eigenvalues and eigenvectors of the circulant matrix. I am not good at doing that in a straight way, i.e. calculating them with a general form of ...
arifle's user avatar
  • 25
0 votes
1 answer
350 views

the associated polynomial of circulant matrix

I tried understanding the circulant matrix with a little more knowledge behind it. In some documents, there is an associated polynomial of the ciculant matrix. $$ g(x) = a_1 + a_2 x+ a_3 x^2 + \cdots +...
arifle's user avatar
  • 25
1 vote
0 answers
45 views

Name or symbol for this simple Laplacian matrix

Is there a special name for a symbol for such Laplacian matrix? $$ \begin{bmatrix} 2 & -1 & 0 & 0 & -1\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0\\ 0&...
whitegreen's user avatar
  • 1,613
0 votes
1 answer
152 views

Diagonalizing a matrix with 4 circulant blocks

I have the following matrix: $$\mathbf{M} = \begin{pmatrix} G_{1}^{(N)} & G_{2}^{(N)} \\ G_{2}^{(N)} & G_{3}^{(N)} \end{pmatrix}$$, where $G^{(N)}_{j}$ are symmetric circulant matrices of size ...
Sl0wp0k3's user avatar
  • 526
0 votes
0 answers
111 views

The square root of symmetric and circulant matrix is symmetric

Let $A$ a circulant symmetric matrix. From the definition of $\sqrt{A}$ it follows that also $\sqrt{A}$ is symmetric ( and circulant ). How can I show the symmetry without using the concept of ...
Giovanni Febbraro's user avatar
0 votes
0 answers
112 views

Power series expansion for a circulant matrix

Let $A$ the block matrix given by the blocks: $$\tilde{A}=\begin{pmatrix} 1&-\mu&0&...&0&-\mu\\ -\mu&1&-\mu&...&0&0\\ 0&-\mu&1&...&0&0\\ ...&...
Giovanni Febbraro's user avatar
3 votes
2 answers
273 views

Eigenvalues of a particular block circulant matrix

I need to compute all the eigenvalues of the following block-circulant matrix for a research. Can anyone help me compute the eigenvalues of the following matrix? $$\left[\begin{array}{l}2I&-I&...
Probabilist's user avatar
0 votes
0 answers
87 views

Square root of a circulant block matrix

I'm trying to show the following: Given the following $n\times n$ symmetric circulant matrices $$A^*=\begin{pmatrix} 1 & -\mu_a & 0 & ...&0&-\mu_a \\ -\mu_a & 1 & -\mu_a &...
Giovanni Febbraro's user avatar
0 votes
1 answer
569 views

Proving an identity for circulant matrices

In my studies of linear algebra, I have encountered this exercise Let $A$ be a circulant matrix defined as $$ A_{jl} = \left\{\begin{array}{cc} r_{l-j} & l\ge j, \\ r_{N+l-j} & l<j\...
Croc2Alpha's user avatar
  • 3,847