Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.


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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.