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.
106
questions
0
votes
1
answer
41
views
Inverse circulant matrix is circulant
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_{...
- 15
1
vote
1
answer
25
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,019
1
vote
1
answer
24
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$. ...
- 267
0
votes
1
answer
22
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 ...
- 87
0
votes
0
answers
9
views
inverting a tridiagonal circulant matrix with alternating elements
First of all, I want to underline that my knowledge regarding matrices is extremely restricted.. It just so happens that they are popping out everywhere in a recent project of mine.
So, in this ...
1
vote
1
answer
46
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 ...
- 19
2
votes
1
answer
62
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
0
votes
0
answers
29
views
Diagonalizing a Circulant Matrix
I know that a Circulant matrix $H$ can be written as $H=Q^* \Lambda Q$ where $Q^* \text{and }Q$ are the IDFT and DFT matrices, and $Q^*Q = I$. Also, I know that elements of $Q = [\alpha_{ij}] = $ Nth ...
- 119
0
votes
0
answers
100
views
Banded circulant matrix with phase shifts
Suppose I have a matrix of the form
$$\mathbf{X} = \begin{bmatrix}
a_1 & 0 & 0 & 0 &0 & a_2e^{i5\pi/3}\\
a_2 & a_1 & 0 & 0 &0 & 0\\
0 & a_2e^{i\pi/3} & ...
- 1
0
votes
0
answers
35
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
58
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
43
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,361
0
votes
1
answer
72
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 ...
- 414
0
votes
0
answers
49
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
43
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
54
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
153
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,823
3
votes
1
answer
87
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 ...
- 518
0
votes
1
answer
85
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 ...
- 289
0
votes
1
answer
32
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^{...
- 91
2
votes
0
answers
75
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
136
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
103
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 ...
- 1
0
votes
2
answers
84
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 \\...
- 674
1
vote
0
answers
87
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
3
votes
1
answer
304
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\...
- 325
0
votes
0
answers
63
views
Given input signal $s$ and convolution kernel $a$, find the corresponding convolution matrix and the output signal
Determine the discrete convolution of the signal $s = (9 \ \ 9 \ \ 6 \ \ 9)^T$ and the convolution kernel $a = (2 \ \ 3 \ \ 1 \ \ 5)^T$. Given the convolution matrix $A \in \mathbb{R^{4 \times 4}}$, ...
- 1,850
1
vote
0
answers
60
views
Generalized Eigenvectors of a real symmetric circulant matrix
I know that the eigenvectors and eigenvalues of any circulant matrix have a nice general form (See the wikipedia page). The wikipedia page also generalizes the eigenvalues (but not eigenvectors) for ...
- 1,474
0
votes
1
answer
313
views
Flux of Curl with given function
Let $F$ from $R^3$ to $R$ defined by $F(x, y, z) = (x − yz, xz, y)$.
Let $S$ be the surface obtained by rotating the graph of $x=2^z+3^z$ with $z ∈ [0, 1]$, around
the $z$-axis (with normal vectors ...
- 192
0
votes
1
answer
213
views
Fourier transform of circulant or cyclic permutation matrix
I understand that a circulant is expanded as a polynomial in P
$$C = C_{0} P + C_{1} P^{2} + \dots + C_{n} P^{n}$$
I also know that the columns of the Fourier matrix $F$ are the eigenvectors of $P$ ...
- 1
6
votes
0
answers
120
views
The number of unitary circulant matrices over a finite field $\mathbb{F}_{q^2}$
Suppose $\mathbb{F}=\mathbb{F}_{q^2}$, where $q$ is a prime power. The conjugate of elements in $\mathbb{F}$ is defined by $\overline{x}=x^q$. I need to find the number of $n\times n$ unitary ...
- 2,846
2
votes
2
answers
72
views
Number of invertible elements in $\mathbb{F}_q[X]/\langle X^p-1\rangle$ with $p=\operatorname{char} \mathbb{F}_q$
I need to find the number of invertible elements in $\mathbb{F}_q[X]/\langle X^p-1\rangle$ with $p=\operatorname{char} \mathbb{F}_q$, which is equal to the number of invertible $p\times p$ circulant ...
- 2,846
1
vote
1
answer
127
views
Can we relate this class of matrices to circulant matrices?
I was having a look into circulant matrices, in particular very simple ones where, for each column, only one entry of the matrix is one. e.g. for a simple 3-dimensional case:
$$
A=\begin{bmatrix}
0 &...
- 369
3
votes
1
answer
165
views
Modifying circulant Latin Squares
Question: Given a $N \times N$ circulant Latin square, $M$, is there a sequence of algorithmic modifications that one can make to $M$ such that the main diagonal will consist of exactly $2$ distinct ...
- 874
0
votes
0
answers
24
views
Filling a circulant matrix with certain fixed numbers
Consider a symmetric circulant matrix with entries in each diagonal , sub and superdiagonal being either $0$ or $1$. Example:
$$\begin{bmatrix}1&1&0&1&0&1\\1&1&1&0&...
- 6,567
0
votes
0
answers
123
views
What are the eigenvalues and eigenvectors of this circulant tridiagonal matrix?
\begin{equation}
\begin{pmatrix}
\alpha & \beta & 0 & \dots & 0 & 0 & \beta \\
\beta & \alpha & \beta & \dots & 0 & 0 & 0 \\
...
- 185
1
vote
3
answers
1k
views
Eigenvectors and Eigenvalues of Shift Matrix
$$S:\mathbb{C}^n\rightarrow\mathbb{C}^n, $$
$$S(x_1,x_2,...,x_n)^T = (x_n,x_1,...,x_{n-1})^T.$$
How can the eigenvalues and eigenvectors of S be calculated?
I already have the standard matrix of S ...
- 27
0
votes
1
answer
109
views
Quick way of finding the eigenvalues of circulant matrices over finite fields [closed]
Is there a fast way to find eigenvalues of a circulant matrix over finite field?
Thanks.
- 91
-1
votes
3
answers
230
views
Singular Circulant Matrix
Reffering to the above text, $C(a_0, ..., a_{n-1})$ or $C$ is a $n\times n$ circulant matrix over complex number.
Why $f(x)$ and $1-x^n$ have a common zero if and only if $C$ is singular.
In addition, ...
- 91
0
votes
1
answer
76
views
What's the probability a 3x3 circulant matrix with natural coefficients < n is nonsignular?
What's the probability a $3 \times 3$ circulant matrix with natural coefficients $< n$ is nonsignular?
A circulant matrix $C$ has the form:
$$C = \begin{bmatrix}
c_0 & c_1 & c_2 \\
c_2 &...
- 5,921
3
votes
2
answers
433
views
Simple formula for determinant of circulant matrix built on an arithmetic sequence.
Let $a$ be an arithmetic sequence:
$$a_i=a_1+\lambda(i-1),\tag1$$
and consider a $n\times n$ circulant matrix $M_{n}(a)$ "built" on rotational shifts of the sequence $a$, i.e. with elements:
$$M_{ij}=...
- 23.6k
1
vote
0
answers
50
views
Volume of the convex hull of the rows of a circulant matrix
What is the formula for volume of the convex hull of the rows of a circulant matrix?
- 165
0
votes
0
answers
68
views
why the inverse of a circulant matrix is circulant?
Does any body know why the inverse of a circulant matrix is circulant? is there any reference or easy proof for that?
- 165
1
vote
0
answers
48
views
How to recover sparse circulant matrix based on its partial eigenvalues?
Suppose we have a right circulant matrix ($n \times n$)
$$
C=
\begin{bmatrix}
c_0 & c_{n-1} & c_{n-2} & \cdots & c_1\\
c_1 & c_0 & c_{n-1} & \cdots & c_2\\
...
- 11
5
votes
1
answer
540
views
Rank of circulant matrix with $k$ ones per row
Consider the $n\times n$ matrix over the field $\mathbb F_2$ formed by creating the circulant matrix of the vector consisting of $k$ ones followed by $n-k$ zeroes. E.g., for $n=4$ and $k=2$, the ...
- 45.8k
0
votes
0
answers
90
views
find the trace of a $D^{-1}$ in $A=(B+C)D^{-1}$
Let
$$B := \begin{bmatrix} j H & kH \\ kH & H\end{bmatrix}$$
where $H$ is a circulant matrix and it is symmetric and non-invertible, and $j, k$ are scalars. Let
$$A := (B+C)D $$
where $C$ ...
0
votes
1
answer
519
views
Eigenvector of Laplacian of ring graph [duplicate]
I know the eigenvectors of the Laplacian of a ring graph with $n$ vertices are
$$x_k(u) = \sin \left( \frac{2 \pi k u}{n} \right)$$
and
$$y_k(u) = \cos \left( \frac{2 \pi k u}{n} \right)$$
for $1 \...
- 510
2
votes
0
answers
41
views
"Circulant" matrices of arbitrary step size, do they also have special basis?
Circulant matrices are famous because they are diagonalized by vectors being the basis functions to the Discrete Fourier Transform.
But what happens if we slightly modify a circulant matrix, so that ...
- 24.1k
2
votes
1
answer
178
views
Are these anti-circulant matrices?
Consider the matrix
\begin{pmatrix}1&k+2&2&k+3&\ldots&2k+1&k+1\\k+2&2&k+3&3&\ldots&k+1&1\\\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&...
- 6,567
0
votes
1
answer
70
views
A certain power of a matrix is Identity
I have a vector say $v=[1 1 1 1 1 0 0 0]$ with this i generate a circulant matrix if order $8\times 8$. Now i see that the circulant matrix generated by this matrix has a property that $$ M^4\equiv I~\...
- 2,567