# Daily Archives: April 17, 2009

## Matrix Decomposition by Discrete Fourier Transform

Given a 3-vector of complex numbers, (A,B,C), define its discrete Fourier transform as
$(a,b,c) = (A+B+C,A+wB+w^*C,A+w^*B+wC)$
where $w = \exp(2i\pi/3)$. That is, I’ll use lower case letters to denote the discrete Fourier transforms of UPPER case letters. The above leaves off a factor of $\sqrt{1/3}$ but it will do.

Of interest today will be vectors (A,B,C) which happen to satisfy A+B+C = 0. These are eigenvectors of the Democratic D matrix

Democratic matrix with all entries D

that is, the matrix all of whose entries are equal to the complex number D. Of course their eigenvalues are zero. None of this is particularly interesting until we move from linearity to bilinearity and work with the discrete Fourier transforms of 3×3 matrices.

Define the Fourier transform of a 3×3 matrix U as $u = F^{-1}UF/3$ where $F$ is the matrix:

Discrete Fourier transform matrix

where $w = \exp(2i\pi/3)$. With this definition, the discrete Fourier transform of the democratic matrix D, is:

Fourier transform of democratic matrix

This is a nice simplification.

Now let A+B+C=0 and compute some discrete Fourier transforms of four kinds of matrices, 1-circulant, 2-circulant, and two new types I will call “bra” and “ket” for obvious reasons. Untransformed matrices on the left, their transforms on the right, note that they fit together like the pieces of a jigsaw puzzle: