# 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.

-

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

-
Thanks Siva. Here is a couple of questions: –  mghandi May 28 '11 at 14:31
For the case b=2, the eigenvectors are mutually orthogonal, but for the general b, the eigenvectros constructed by the above process are not necessary orthogonal, for example for b=3,L=2,k=1, we have both [1,-1,0,0,0,0] and [1,0,-1,0,0,0]. is there a way to construct an orthogonal set? –  mghandi May 28 '11 at 14:38
Can you please give me some references where I can find more about this or similar stuffs. –  mghandi May 28 '11 at 14:57