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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
248 views

Two questions about three circulant matrices

Consider the following matrix equation in $n \times n$ circulant $\pm 1$ matrices $A$, $B$, $C$ $$2AA^T+BB^T+CC^T=(4n+4)I-4J$$ where $I$ is the $n \times n$ identity matrix and $J$ is the $n×n$ matrix ...
user369335's user avatar
1 vote
0 answers
64 views

Circulant matrix inverse in $GF(p)$

For a polynomial $C(x)=c_0+\dots+c_n x^n$, consider a circulant matrix $C$ such that $$ C= \begin{pmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 &...
Oleksandr  Kulkov's user avatar
2 votes
1 answer
106 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}$ ...
ABB's user avatar
  • 3,898
3 votes
1 answer
218 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 ...
Annie's user avatar
  • 71
1 vote
0 answers
127 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 ...
ABB's user avatar
  • 3,898
9 votes
1 answer
598 views

One question on circulant $\pm1$ matrices

Let $n > 13$ be a positive integer. Is there any $n \times n$ circulant $\pm1$ matrix $A$ satisfying the following property $$AA^T=(n-1)I+J$$ where $I$ is the $n \times n$ identity matrix and $J$ ...
user369335's user avatar
1 vote
1 answer
119 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}$ ...
gabriel's user avatar
  • 31
0 votes
0 answers
107 views

Square root of a circulant matrix block

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
2 votes
1 answer
292 views

The number of unitary circulant matrices over a finite field $\mathbb{F}_{q^2}$

I asked this question in MSE few days ago but there was no response. Suppose $\mathbb{F}=\mathbb{F}_{q^2}$, where $q$ is a prime power. The conjugate of elements in $\mathbb{F}$ is defined by $\...
Groups's user avatar
  • 369
0 votes
1 answer
221 views

Is the random point $(C,S)$ the same as $(1,0)+(\cos U,\sin U)=(1 + \cos U,\sin U)$, with $U$ a uniform r.v.?

Suppose that $\theta_1$ and $\theta_2$ are independent and identically distributed (i.i.d.) random variables and that $\theta_j$ has probability density function (PDF) $f_j = \frac{1}{2\pi}$ ($i.e.$, ...
Felipe Augusto de Figueiredo's user avatar
0 votes
1 answer
124 views

Chromatic Polynomials of Circulant Graph With Two Parameters

I have been working with the chromatic polynomials of circulant graphs of prime order $p$ with two distinct parameters, i.e. $P_{p,i,j}(x):= P(C_{p}(i,j),x)$ with $1 \leq i \neq j \leq \ n/2.$ In ...
Abraham G's user avatar
6 votes
1 answer
272 views

An Optimization Problem with Complex Variables, regarding Eigenvalues of Circulant Matrices

Let $S$ be a finite subset of the complex unit circle and $1 \in S$. For each $n \in \mathbb N $, define $f_n\colon S^{n-1}\to\mathbb R$ by $$f_n(x) := \sum_{w^{n}=1}|x_1w+ x_2w^2\cdots+x_{n-1}w^{n-1}...
Mahdi's user avatar
  • 1,991
4 votes
1 answer
304 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 ...
Seva's user avatar
  • 22.8k
1 vote
0 answers
110 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 ...
nahila's user avatar
  • 93
3 votes
1 answer
534 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 ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
364 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\}$ ...
Simd's user avatar
  • 3,195
7 votes
1 answer
1k views

Are there infinite constructions for partial circulant Hadamard matrices?

I believe that the circulant Hadamard conjecture (that there are no circulant Hadamard matrices of size greater than $4\times4$) is still open. I also know that examples of $(n/2) \times n$ matrices ...
kodlu's user avatar
  • 10.1k
6 votes
0 answers
131 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-...
Diane's user avatar
  • 71
1 vote
0 answers
74 views

About the rank of a Pell equation-related matrix

I have a question about the solution of Pell-equation over a prime field. I want prove that the matrix $M$ is of rank $\frac{p-1}{2}$, with $M=(m_{i,j})\in\left(\mathbb{Z}/(p^p-1)\mathbb{Z} \right)^{(...
Diane's user avatar
  • 71
4 votes
2 answers
495 views

XOR circulant matrices?

Take a function $f: Z_N\rightarrow R$. Construct an $N \times N$ matrix where the $(i,j)$th element of the matrix is $f(i-j)$, where $i-j$ is interpreted mod $Z_N$. The resulting matrices are ...
Bill Bradley's user avatar
  • 3,809
1 vote
1 answer
531 views

Partial Vandermonde circulant determinant expression

Consider following partial Vandermonde type, circulant matrix $\begin{bmatrix} x_1 & x_2 & 0 & \dots & 0 & x_n\\ x_1^2 & x_2^2 & x_3^2 & \dots & 0 & 0\\ \vdots ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
145 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 ...
pre-kidney's user avatar
  • 1,289
6 votes
2 answers
437 views

Is a normal matrix satisfying $A^TA=...$ circulant?

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\\ \...
pre-kidney's user avatar
  • 1,289
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 ...
Simd's user avatar
  • 3,195
0 votes
1 answer
319 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 &...
Felix Goldberg's user avatar
1 vote
0 answers
195 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 ...
Felix Goldberg's user avatar
14 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 &...
user22127's user avatar
  • 143
1 vote
2 answers
523 views

Is this general form of Lovasz theta function of circulant graphs?

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}$? ...
Turbo's user avatar
  • 13.7k