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
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$...
hbghlyj's user avatar
  • 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 ...
Andreas's user avatar
  • 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 & \...
NitaStack's user avatar
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 ...
eagle I 's user avatar
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 ...
Matthew James's user avatar
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^{-...
Matthew James's user avatar
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 ...
Matthew James's user avatar
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 ...
koko's user avatar
  • 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 ...
user3284182's user avatar
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 ...
user3284182's user avatar
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 \...
mlbj's user avatar
  • 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 &...
Sam's user avatar
  • 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)...
Matthew James's user avatar
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 &...
Mhetre's user avatar
  • 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 ...
mrx king's user avatar
  • 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 ...
Tomm's user avatar
  • 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?
Rylan Schaeffer's user avatar
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 ...
Betelgeuse's user avatar
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 ...
Physics Enthusiast's user avatar
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 & ...
Tapi's user avatar
  • 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{...
Xinyu Chen's user avatar
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 &...
Xinyu Chen's user avatar
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} \...
Ptch's user avatar
  • 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 & \...
MathLearner's user avatar
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}...
LaguerreGroup's user avatar
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 ...
Sl0wp0k3's user avatar
  • 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_{...
ThatBoi's user avatar
  • 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} ...
a_student's user avatar
  • 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$. ...
Jones's user avatar
  • 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 ...
G. Ticher's user avatar
  • 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 ...
sujikin's user avatar
  • 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 &...
Yauhen Yakimenka's user avatar
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 &...
Blake's user avatar
  • 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 ...
arifle's user avatar
  • 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 +...
arifle's user avatar
  • 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&...
whitegreen's user avatar
  • 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 ...
Sl0wp0k3's user avatar
  • 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 ...
Giovanni Febbraro's user avatar
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\\ ...&...
Giovanni Febbraro's user avatar
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 &...
Giovanni Febbraro's user avatar
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\...
Croc2Alpha's user avatar
  • 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 ...
Zara's user avatar
  • 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 ...
MRule's user avatar
  • 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^{...
darisoy's user avatar
  • 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 ...
Mikail Khona's user avatar
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 ...
Parth's user avatar
  • 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 ...
Bots Fab's user avatar
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 \\...
Math_Is_Fun's user avatar
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. ...
Jenny Y's user avatar
  • 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\...
ECA18's user avatar
  • 387