Why is a BCCB matrix completely specified by its first column?

Question

It is claim in some literature that a Block Circulant with Circulant Block (BCCB) matrix is completely specified by its first column.(e.g. here )

But I have a contradictory example:

Let $c = [1, 2, 3, 4, 5, 6]^T$ be the first column of a BCCB matrix, so we can construct the following two different BCCB matrix by $c$:

$$ A = \left( \begin{array}{ccc|ccc} 1 & 3 & 2 & 4 & 6 & 5\\ 2 & 1 & 3 & 5 & 4 & 6\\ 3 & 2 & 1 & 6 & 5 & 4\\ \hline 4 & 6 & 5 & 1 & 3 & 2\\ 5 & 4 & 6 & 2 & 1 & 3\\ 6 & 5 & 4 & 3 & 2 & 1 \end{array} \right) $$

$$ B = \left( \begin{array}{cc|cc|cc} 1 & 2 & 5 & 6 & 3 & 4\\ 2 & 1 & 6 & 5 & 4 & 3\\ \hline 3 & 4 & 1 & 2 & 5 & 6\\ 4 & 3 & 2 & 1 & 6 & 3\\ \hline 5 & 6 & 3 & 4 & 1 & 2\\ 6 & 5 & 4 & 3 & 2 & 1 \end{array} \right) $$

Please help me. Thanks.

It is true that it is determined by the first column, IF you know the size of the blocks -- since the part of the first column that lies in each block determines that block uniquely, and analogously knowing the first "columns" of the block decomposition determines the rest. But yes, your example seems to show that the first column alone isn't enough, without knowledge of the block size. — Nick Peterson, May 25 '15 at 07:42

score 1 · Answer 1 · edited Apr 13 '17 at 12:21

A block circulant matrix is indeed specified by only its first column. This is simply a matter of understanding the degree of freedom of the BCCB matrix.

Now to your question, yes both the BCCB matrix A and B are indeed determined by their first column alone, however due to the different block arrangements from the first column, the eigenvalues obtained will be different.

Consider your case, A and B are mostly similar matrices except in the ordering of the blocks which will affect the eigenvalues, they are not the same since the Fourier based decomposition of it does change because you have partitioned it differently,

$A = F^*D_1F$ , $B = F^*D_2F$, and $D_1 \neq D_2$

where F is two dimensional unitary discrete Fourier transform (DFT) matrix and D is the diagonal vector that represents the eigenvalues of the BCCB matrix. This is because, to compute eigenvalues of A or B, we need only multiply F by the first column of A or B. The eigenvalues can be computed by applying $fft2$ to array containing the first column of $A$ arranged in matrix form as $M \times N$ and for $B$ the arrangement of the first column is different $N \times M$. You can check this effect of ordering numerically (example using MATLAB),

 M = 4; N = 7; Arr = rand(1, M*N)
 A= reshape(Arr, [M,N])

A =

0.2290    0.5383    0.1067    0.8173    0.2599    0.1818    0.8693
0.9133    0.9961    0.9619    0.8687    0.8001    0.2638    0.5797
0.1524    0.0782    0.0046    0.0844    0.4314    0.1455    0.5499
0.8258    0.4427    0.7749    0.3998    0.9106    0.1361    0.1450

B = reshape(Arr, [N,M])
B =

0.2290    0.4427    0.0844    0.2638
0.9133    0.1067    0.3998    0.1455
0.1524    0.9619    0.2599    0.1361
0.8258    0.0046    0.8001    0.8693
0.5383    0.7749    0.4314    0.5797
0.9961    0.8173    0.9106    0.5499
0.0782    0.8687    0.1818    0.1450

fftB = reshape(fft2(B) , [ M*N], 1)
fftA = reshape(fft2(A) , [ M*N], 1)
fftA = 
   13.4672 + 0.0000i
   1.5558 - 1.7488i
  -4.5698 + 0.0000i
   1.5558 + 1.7488i
   0.0461 - 0.9230i
  -0.3759 - 0.8773i
   0.1893 + 2.4168i
   0.4282 - 0.2557i
   1.7165 + 0.3914i
   0.4915 + 0.7909i
  -0.6638 + 1.3152i
  -0.2346 + 0.4059i
  -1.0745 + 1.1407i
  -1.2346 - 0.2051i
  -1.9929 - 1.1924i
  -0.0943 - 1.5778i
  -1.0745 - 1.1407i
  -0.0943 + 1.5778i
  -1.9929 + 1.1924i
  -1.2346 + 0.2051i
   1.7165 - 0.3914i
  -0.2346 - 0.4059i
  -0.6638 - 1.3152i
   0.4915 - 0.7909i
   0.0461 + 0.9230i
   0.4282 + 0.2557i
   0.1893 - 2.4168i
  -0.3759 + 0.8773i

fftB =
   13.4672 + 0.0000i
  -2.6210 + 1.4154i
  -0.9144 - 0.9124i
   0.3715 - 1.6765i
   0.3715 + 1.6765i
  -0.9144 + 0.9124i
  -2.6210 - 1.4154i
   0.6651 - 1.2875i
   0.7972 - 1.2250i
   0.3130 + 0.6270i
   1.5328 - 0.7320i
  -2.0687 - 0.0529i
  -0.0013 + 2.1249i
  -0.2263 - 0.7066i
   0.1352 + 0.0000i
  -0.4997 - 0.7173i
  -0.1009 - 1.4119i
  -0.8427 - 2.8536i
  -0.8427 + 2.8536i
  -0.1009 + 1.4119i
  -0.4997 + 0.7173i
   0.6651 + 1.2875i
  -0.2263 + 0.7066i
  -0.0013 - 2.1249i
  -2.0687 + 0.0529i
   1.5328 + 0.7320i
   0.3130 - 0.6270i
   0.7972 + 1.2250i

If you make a BCCB circulant matrix of size $MN \times MN$ in

blocks of $M \times M$ for $N \times N$ circulant structure, (for A in your case, M= 3, N = 2)
blocks of $N \times N$ for $M \times M$ circulant structure, (for B again in your case, N=2, M = 3)

then the product of the BCCB matrix when multiplied by a vector say $x$ does change, so does its inverse, and so does its Fourier based decomposition. It still depends only on the first column though, which has $M \times N$ unique elements, which in turn is the number of degrees of freedom of the matrix. For A and B, whether it is $3 \times 2$ or $2 \times 3$, it doesn't matter, 6 elements are the only unique numbers that matter, but the eigenvalues computed using different arrangements of total 6 elements in form $3 \times 2$ or $2 \times 3$ will differ.

This problem will not occur when you have a perfect square arrangement, i.e. when $M = N$ and the BCCB matrix is of form $N^2 \times N^2$ (see. square circulant problem)

Why is a BCCB matrix completely specified by its first column?

1 Answers1