I have the following Matrix
$$A = \begin{pmatrix} X \\ Y \end{pmatrix}$$
Where X, and Y are circulant Matrices. I want to diaganlize $AA^T$.
I tried the following:
$$AA^T = \begin{pmatrix} X \\ Y \end{pmatrix} \begin{pmatrix} X^T & Y^T \end{pmatrix} =\begin{pmatrix} XX^T & XY^T\\ YX^T & YY^T \end{pmatrix}$$
Now it is easy to show that $XY^T$ and obviously $YX^T$ are both circulant. I end up with a general 2*2 block Matrix that is symmetric and block circulant as follows: $G = \begin{pmatrix} X & K\\ K^T & Y \end{pmatrix}$ Now {X,K,Y} are all circulant. The question is how to diagnalize the final Matrix G efficiently.
My approach is as follows. Since each circulant Matrix can be diagnalized using the columns of the DFT matrix (F) (i.e $X = FDF^H$) Where D is diagonal and X is circulant.
Then I can re-write G as follows:
$$G = \begin{pmatrix} F & 0\\ 0 & F \end{pmatrix} \begin{pmatrix} D_x & D_k\\ D_k & D_y \end{pmatrix} \begin{pmatrix} F^H & 0\\ 0 & F^H \end{pmatrix} $$
I stopped at this point since I don't know how to efficiently diagonalize \begin{pmatrix} D_x & D_k\\ D_k & D_y \end{pmatrix} using the the eignes of the blocks.
Maybe there is a more direct approach that can result into diagnalizing the block circulant matrix from the beginning. Note, in general my matrix is NOT BCCB(Block Circulant with Circulant Blocks) because X $\neq$ Y in general.