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