# Questions tagged [circulant-matrices]

A circulant matrix is a square matrix where each row has the same elements as the previous row, cyclically rotated right by one element. It is a specific kind of a square Toeplitz matrix.

24 questions
Filter by
Sorted by
Tagged with
99 views

### The eigenvectors of adding a particular rank one matrix to the circulant matrix

Suppose that $e_1, \cdots, e_n$ are the standard vectors of the Euclidean space $\mathbb{R}^n$. Let us consider the backward shift operator $T:\mathbb{R}^n\to \mathbb{R}^n$ given by $Te_k=e_{k-1}$ ...
138 views

### Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries

I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
1 vote
91 views

### What are the eigenvalues/eigenvectors of the matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^{\frac{n-1}{2}}$ when $n$ is odd?

Suppose that $n$ is odd. The eigen values/eigenvectors of the skew-circulant matrix $A=\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$ are successfully computed in this post. Q. What are ...
1 vote
110 views

### Define circulant matrix using matrix-vector multiplication? [closed]

Does there exist a matrix $\mathbf{A}$ that takes any vector $\mathbf{v}\in \mathbb{R}^n$ into the circulant matrix $\mathbf{C}_{\mathbf v} = \mathbf{A}\mathbf{v} \in \mathbb{R}^{n\times n}$ ...
96 views

282 views

### Large submatrices of circulant matrices

What properties of circulant matrices are inherited by their principal submatrices? To be more specific: Given a square (zero-one) matrix $M$ of order $n$ with all elements on its main diagonal ...
1 vote
107 views

### Fullrankness of sum of time shifts

I am working with finite Gabor frames and in this context a problem appeared which I am trying to solve for a couple of weeks now. Given a $(p,k,1)$ cyclic difference set for $\mathbb{Z}_p$ which is ...
494 views

### Lovasz theta and circulant graphs

Let $\theta(G)$ denote Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be Lovasz upper bound for $\theta(G)$. Let $C_{2n+1}$ denote cycle graph with $2n+1$ nodes. We know following two ...
352 views

### Bounds for maximum determinant of circulant matrices

The Hadamard circulant conjecture states that there do not exist circulant Hadamard matrices with more than $4$ columns. An $n$ by $n$ Hadamard matrix where the entries are chosen from $\{-1,1\}$ ...
130 views

### About the properities of sum of powers of items in a polynomial

Given a polynomial $f_1=a_1x+a_2x^2+\cdots+a_{p-1}x^{p-1}\in\mathbb{Z}[x]/(x^{p}-1)$, with prime $p$, we may generate the other $p-1$ polynomials: \begin{eqnarray*} f_2&=&a_1^2x^2+\cdots+a_{p-...
1 vote
73 views

1 vote
137 views

### Are certain normal matrices circulant? (Part 2)

Let $\mathcal{F}$ denote the family of real normal matrices $A$ such that $A^TA=\begin{pmatrix} a & b \\ b & \ddots \end{pmatrix}$, for $b>0$. As a user observed in the solution of Part 1 ...
Let $A=\{a_{ij}\}$ be a normal matrix such that $a_{ij}\geq 0$ with equality iff $i=j$. Suppose that $$A^TA=\begin{pmatrix} a & b & \cdots & b\\ b & a & \ddots & \vdots\\ \... 8 votes 2 answers 2k views ### How to determine if there exists a non-zero vector in the kernel If you are given a 0-1 circulant matrix with n rows and n columns, is there an efficient way of determining if there exists a non-zero \{-1,0,1\}-vector in its kernel? Could this problem ... 0 votes 1 answer 288 views ### Graphs with circulant distance matrices The cycle has this property. For instance, the distance matrix for a 6-cycle is: A=\begin{bmatrix} 0 & 1 & 2 & 3 & 2 & 1 \\\\ 1 & 0 & 1 &... 1 vote 0 answers 190 views ### bounds on the entries of an inverse circulant matrix Suppose that C is a (real) circulant invertible matrix defined by a vector d. Then C^{-1} is also a circulant defined by some vector f. There exists a standard formula that expresses the ... 13 votes 4 answers 7k views ### Eigenvectors and eigenvalues of a tridiagonal Toeplitz matrix Is it possible to analytically evaluate the eigenvectors and eigenvalues of the following n \times n tridiagonal matrix$$ \mathcal{T}^{a}_n(p,q) = \begin{pmatrix} 0 & q & 0 & 0 &...
Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by: $\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$? ...