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}$.
 A: 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.
