eigen decomposition of an interesting matrix

Lets define:

$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$.

$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of all different gaped binary sequences with $k$ known bits and $L-k$ gaps.

$A_{M*N}=[a_{i,j}]$ is a binary matrix defined as following:

$$a_{i,j} = \left\{\begin{matrix} 1 & \text{if } v_i \text{ matches } u_j \\ 0 & \text{otherwise } \end{matrix}\right.$$

now, the question is: What are the eigenvectors and eigenvalues of the matrix $S_{M*M}=AA^{T}$?

Here is an example for $L=2, k=1$:

$$U = \left \{ 00,01,10,11\right \} $$ $$V = \left \{ 0.,1.,.0,.1\right \} ^*$$

$$ A = \begin{bmatrix} 1 & 1 & 0 &0 \\ 0 & 0 & 1 &1 \\ 1 & 0 & 1 &0 \\ 0 & 1 & 0 &1 \end{bmatrix}$$

$$ S = \begin{bmatrix} 2 & 0 & 1 &1 \\ 0 & 2 & 1 &1 \\ 1 & 1 & 2 &0 \\ 1 & 1 & 0 &2 \end{bmatrix}$$

For the special case $k=1$, is has been previously solved by joriki and the solution can be found here. See the same reference for a graph analogy of matrix $S$.

Furthermore, it has been shown here by joriki that: $$\text{rank}(AA^{T})=\text{rank}(A)=\sum_{m=0}^k\left({L\atop m}\right)\;\;$$ As for the eigenvalues, numerical values suggest that $AA^{T}$ has $\binom{L}{m}$ eigenvalues equal to $\binom{L-m}{k-m}2^{g}, m=0,..,k$, where $g=L-k$ is the number of gaps.

any comments or suggestion is appreciated.

$^{*}$ here dots denote gaps. a gap can take any value, and each gaped sequence with $k$ known bits and $(L−K)$ gaps in $V$, exactly matches to $2^{L−k}$ sequences in U, hence the sum of elements in each row of $A$ is $2^{L−k}$.

Solution 1:

The eigenvectors corresponding to the non-zero eigenvalues can be listed as follows. For each $m=0,1,...,k$, pick $m$ bit positions from the total $L$. This can be done in $\binom {L} {m}$ ways. Define vector x, with $i^{th}$ element, $x_i$, given by

$x_i = \begin{cases} 1, & \text{if } v_i \text{ has no gaps among the m bits and has even number of 1s among these m bits} \\ -1, & \text{if } v_i \text{ has no gaps among the m bits and has odd number of 1s among these m bits} \\ 0, & \text{otherwise} \end{cases} $

This is an eigenvector for $S = AA^T$ with eigenvalue $\binom {L-m}{k-m}*2^{L-k}$. To show this, we first see that $S_{ij}$ ($ij^{th}$ entry in $S=AA^T$) is the number of elements in $U$ which match both $v_i$ and $v_j$. From the construction of $x$, we can make two observations. First, if $x_i \neq 0$, then $x_j = x_i$ whenever $v_i$ has a common match with $v_j$, that is, whenver $S_{ij}$ is non-zero. Second, if $x_i = 0$, then for each $j_1$ with $S_{ij_1} \neq 0$ and $x_{j_1} \neq 0$, we can find a unique $j_2$ such that $S_{ij_1} = S_{ij_2}$ and $x_{j_1} = - x_{j_2}$. This is because, $x_i = 0$ implies there is a gap among the $m$ bits in $v_i$. So toggling that bit in $v_{j_1}$ gives a $v_{j_2}$ with $S_{ij_1} = S_{ij_2}$ and $x_{j_1} = -x_{j_2}$.

It follows from the second observation above that if $x_i = 0$, then $i^{th}$ entry in $Sx$ is 0. And from the first observation, if $x_i = 1$, then $i^{th}$ entry in $Sx$ is the number of elements in $U$ which match both $v_i$ and $v_j$, summed over all $j$ with $x_j = 1$. This is same as the number of $v_j$ which match $u$, summed over all $2^{L-k}$ different $u$ which match $v_i$. This number can be shown to be $\binom{L-m}{k-m}* 2^{L-k}$. Similar result can be shown for $x_i = -1$ case. So $x$ described above is an eigenvector for $S$ with eigenvalue $\binom{L-m}{k-m}* 2^{L-k}$. As we could choose $m$ bits in $\binom{L}{m}$ ways, we get $\binom{L}{m}$ vectors with this eigenvalue. These vectors can be shown to be mutually orthogonal, hence are linearly independent.

With $m$ varying from $0$ to $k$, we get as many eigenvectors as the rank of the matrix, each with a non-zero eigenvalue. So this gives all the eigenvectors with non-zero eigenvalues.