eigen decomposition of an interesting matrix (general case) Lets define: 
$U=\left \{  u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{  0, 1, .., b-1 \right \}$.
$V=\left \{  v_i\right \} , 1 \leq i\leq M=\binom{L}{k}b^{k},$ the set of all different gaped sequences with $k$ known elements 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 questions are:
i) What is the rank of the matrix $S_{M*M}=AA^{T}$?
ii) What are the eigenvectors and eigenvalues of $AA^{T}$?
Here is an example for $L=2, k=1, b=2$:
$$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$, it has been previously solved by joriki and the solution can be found here.
For the special case of binary sequences $(b=2)$, the rank is given here by joriki, and a solution for the eigen vectors is given here by Siva. 
$^{*}$ here dots denote gaps. a gap can take any value, and each gaped sequence with $k$ known elements and $(L−K)$ gaps in $V$, exactly matches to $b^{L−k}$ sequences in U, hence the sum of elements in each row of $A$ is $b^{L−k}$.
EDIT:
my guess is that $\text{rank}(AA^T)=\text{rank}(A)=\sum_{m=0}^k\left({L\atop m}\right)(b-1)^m\;\;$. and it has $\left({L\atop m}\right)(b-1)^m$ eigenvalues of $\binom{L-m}{k-m}* b^{L-k}$, and the corresponding eigenvectors can be constructed in a similar way as Siva showed for b=2.  
EDIT2: 
using Gram-Schmidt process I obtained the following orthogonal set from Siva's proposed set of eigenvectors. but I wonder if there is a simpler solution too. $$\Delta_{m}^{L,k}=\left[\begin{array}{c|c|cccc}
 & \mathrm{first\, bit\, Not\, picked} &  & \mathrm{first\, bit\, picked}\\
 &  & a_{1}=1 & a_{1}=2 & \cdots & a_{1}=(b-1)\\
\hline 0\ldots & \Delta_{m}^{L-1,k-1} & \Delta_{m-1}^{L-1,k-1} & \frac{1}{2}\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\
\hline 1\ldots & \Delta_{m}^{L-1,k-1} & -\Delta_{m-1}^{L-1,k-1} & \frac{1}{2}\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\
2\ldots & \Delta_{m}^{L-1,k-1} & 0 & -\Delta_{m-1}^{L-1,k-1} & \cdots & \frac{1}{b-1}\Delta_{m-1}^{L-1,k-1}\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
(b-1)\ldots & \Delta_{m}^{L-1,k-1} & 0 & 0 & \cdots & -\Delta_{m-1}^{L-1,k-1}\\
\hline g\ldots & \Delta_{m}^{L-1,k} & 0 & 0 & \cdots & 0\end{array}\right]$$
$\Delta_{m}^{L,k}$ is the matrix containing orthogonal eigenvectors for L,k and m.
 A: I think the guesses you gave above are all correct. The eigenvectors can be constructed similar to the $b=2$ case. For each $m=0,1,..,k$, pick $m$ bits from the total $L$ bits ($\binom{L}{m}$ ways to choose) and pick an $m$-bit vector, $a$, with elements from $\{1,2,..,b-1\}$ ($(b-1)^m$ ways to choose). Define a vector $x$ where $i^{th}$ element $x_i$ is $0$ if $v_i$ has a gap in any of the $m$ bits. And if $v_i$ has no gaps in these $m$ bits, consider the $m$-bit vector (say $b$) formed by these bits in $v_i$ and define $x_i$ as 
$x_i = 
\begin{cases} 
1, & \text{if } b \text{ has even number of non-zero values and if } b_j \neq 0 \implies b_j=a_j \forall j=0,1,..,m\\
-1, & \text{if } b \text{ has odd number of non-zero values and if } b_j \neq 0 \implies b_j=a_j \forall j=0,1,..,m\\
0, & \text{otherwise}
\end{cases}
$
Each of the $\binom{L}{m}*(b-1)^m$ different vectors $x$ defined as above is an eigenvector of $AA^T$, with an eigenvalue of $\binom{L-m}{k-m}*b^{L-k}$. Proof is again similar to $b=2$ case.
Sum of all the eigenvalues obtained above is 
$
\sum_{m=0}^{k} \binom{L}{m} \binom{L-m}{k-m} * b^{L-k}*(b-1)^m = \binom{L}{k}*b^{L-k} \sum_{m=0}^{k} \binom{k}{m}*(b-1)^m = \binom{L}{k}*b^L
$
This is equal to trace of $AA^T$. But $AA^T$ is symmetric positive semidefinite, hence has no negative eigenvalues. So all the remaining eigenvalues of $AA^T$ are $0$. So rank($A$) = $\sum_{m=0}^{k} \binom{L}{m}*(b-1)^m$.
