Let's first consider the case of Block Circulant Matrices with Circulant Blocks (BCCB). These block matrices consist of circulant blocks. If we consider the blocks as elements, the BCCB matrix turns into a circulant one. Let's assume the blocks to have the dimension $n \times n$, and the BCCB matrix to have the dimension $mn \times mn$. In this case, the diagonalization of the BCCB matrix is: $$A = (F_m \otimes F_n)^H D \,(F_m \otimes F_n)$$
$F_j$ is the untiary DFT matrix of size $j\times j$.
Suppose $A$ is now a BTTB matrix of size $mn \times mn$, with blocks of size $n \times n$. Take $M$ as the the smallest power of two such
that $M \geq 2m−1$. Take $N$ as the smallest power of 2 such that $N \geq 2n − 1$. $A$ can be written in the following way: $$A = Q^H D \, Q$$
where $D$ is diagonal with size $MN \times MN$ and Q has size $MN \times mn$.
The columns of $Q$ form a subset of the columns of $F_M \otimes F_N$. The selection of the columns is done the following way
- Consider the columns of $F_M \otimes F_N$ as $M$ blocks of $N$ columns.
- Consider only the first $m$ blocks (The relevant blocks)
- take only the first $n$ columns of each one of the relevant blocks
Example: for $m = 2$ and $n=4$, choose $M = 4$ and $N = 8$. From $F_4 \otimes F_8$ choose columns with indices from $\{1,2,3,4,9,10,11,12\}$
Note that the vector product of a BTTB matrix can be calculated using a two dimensional FFT thanks to the above factorization.
