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.
137
questions
4
votes
0
answers
88
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 $c_0,\dots,c_{n-1}$
$$f_n=\prod_{j=0}^{n-1}\sum_{i=0}^{n-1}ξ^{ij}c_i$...
- 934
0
votes
0
answers
32
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 ...
- 15.3k
0
votes
1
answer
71
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 & \...
- 95
2
votes
0
answers
38
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 ...
- 63
0
votes
0
answers
51
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 ...
- 101
0
votes
0
answers
50
views
Diagonalize block matrix containing circulant and sparse matrices
I have a matrix $Q := I_{2m} - t A$, where
\begin{equation*}
A = \frac{1}{2}
\begin{bmatrix}
GC^{-1}(GC^{-1})^T & -GC^{-1}(GC^{-1})^T \\
-GC^{-1}(GC^{-1})^T & GC^{-1}(GC^{-...
- 101
1
vote
0
answers
86
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 ...
- 101
2
votes
3
answers
264
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 ...
- 41
0
votes
0
answers
51
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 ...
- 59
2
votes
0
answers
32
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 ...
- 59
0
votes
1
answer
79
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 \...
- 131
0
votes
0
answers
23
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 &...
- 1,673
0
votes
0
answers
29
views
Construct Circulant matrix from 2D convolution integral
I have a known function $d(x,y) = \frac{k}{\sqrt{x^2+y^2}+k}$ where ($k = $constant). I also have the 2D convolution integral:
\begin{equation}
\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} w(x_0,y_0)...
- 101
1
vote
0
answers
46
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 &...
- 19
8
votes
3
answers
198
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 ...
- 161
5
votes
0
answers
62
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 ...
- 71
0
votes
0
answers
7
views
Measuring real square matrix's deviation from being circulant?
What metrics or measurements exist for determining how much a (real square) matrix deviates from being circulant?
- 453
3
votes
1
answer
66
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 ...
- 484
1
vote
0
answers
53
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 ...
0
votes
0
answers
57
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 & ...
- 1,661
0
votes
0
answers
72
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{...
- 107
1
vote
1
answer
118
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 &...
- 107
1
vote
0
answers
21
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} \...
- 11
1
vote
1
answer
104
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 & \...
- 513
2
votes
1
answer
186
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}...
0
votes
0
answers
51
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 ...
- 516
-1
votes
1
answer
119
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_{...
- 13
1
vote
1
answer
58
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} ...
- 1,394
1
vote
1
answer
41
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$. ...
- 277
0
votes
1
answer
40
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 ...
- 135
1
vote
1
answer
79
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 ...
- 119
2
votes
1
answer
88
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 &...
- 517
2
votes
3
answers
477
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 &...
- 107
0
votes
0
answers
48
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 ...
- 25
0
votes
1
answer
196
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 +...
- 25
1
vote
0
answers
44
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&...
- 1,533
0
votes
1
answer
115
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 ...
- 516
0
votes
0
answers
82
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 ...
0
votes
0
answers
89
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\\
...&...
0
votes
0
answers
71
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 &...
0
votes
1
answer
403
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\...
- 3,837
3
votes
1
answer
107
views
Showing that these algebras are isomorphic
This paper (page 157) diagonalized circulant matrix $S$ like this where $\psi$ is an eigenvalue and $\Omega$ is composed of the eigenvectors as columns:
$$
\Omega^{-1}S\Omega =
\begin{bmatrix}
\psi_0 ...
- 580
0
votes
1
answer
119
views
Efficient product of vector with inverse of positive definite circulant matrix plus real diagonal matrix?
Question:
Hi! Would anyone happen to know an efficient way to compute:
$$
u^\top [C + D]^{-1},
$$
where:
$C$ is a square matrix, and is real, positive definite, and circulant
$C$ is too large to fit ...
- 381
0
votes
1
answer
55
views
Eigenvalues of circulant using spectral mapping
Is there a way to utilize the spectral mapping theorem to find the eigenvalues of a circulant matrix if eigenvectors of P are known?
From this wiki page, I know that $C=c_0I+c_1P+c_2P^2+...+c_{n-1}P^{...
- 121
2
votes
0
answers
122
views
Eigenvectors of perturbed circulant matrix
I have a circulant matrix defined by a positive kernel W(x):
$W_{ij} = W(|i-j|)$
where W is defined on positive reals (so we are sampling {1,2,...,N} to create the matrix). I know this has ...
- 31
0
votes
0
answers
333
views
More information about Circulant matrix diagonalized in the Fourier basis
I read that a circulant matrix $C$ can be written as $F \phi F^{-1}$ where $\phi$ are $C$'s eigenvalues. Can someone give me more information about the $F$ matrix? Will it be the same for any ...
- 119
0
votes
1
answer
163
views
How do I determine which connections form cycles in a directed graph's adjacency matrix?
given a matrix A I know I can perform A^n = path length from j to v for some entry [j,v] to find paths to v. As I perform this iteration for ...
- 11
0
votes
2
answers
95
views
Calculating determinants from matrices
$[10$ points $]$ Let $P$ be a $n \times n$ matrix, where the entries of of $P=\left(p_{i j}\right)$ are as follows:
$$
p_{i j}=\left\{\begin{array}{l}
1 \text { if } i=j+1 \\
1 \text { if } i=1, j=n \\...
- 694
1
vote
0
answers
130
views
Make eigenvalues of block circulant matrix plus diagonal matrix in the left half plane
$\boldsymbol A$ and $\boldsymbol B$ are $2\times 2$ matrices. $\boldsymbol 0$ refers to a $2\times 2$ zero matrix.
$\boldsymbol C$ is a block circulant matrix with $2n$ dimensions. $n$ is variable.
...
- 21
4
votes
1
answer
665
views
Can the eigenvalues of this block circulant matrix be found?
I have a matrix of the form
$$ M = \begin{pmatrix} A & A^T & & & I\\ I & A & A^T & & \\ & I & A & \ddots &\\ & & \ddots & \ddots & A^T\...
- 387