Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
thanks Siva. For a related question, please also see this: math.stackexchange.com/questions/32490/any-pattern-here-revised –  mghandi Apr 12 '11 at 15:33
    
there seems to be a typo on eigenvalue on first line following $x_i$ definition. It should be $\binom{L-m}{k-m}$ instead of $\binom{L}{k-m}$ –  mghandi Apr 12 '11 at 19:04
    
yes.. thanks for the correction –  Siva Apr 13 '11 at 2:51
    
just added a new post for the general case: math.stackexchange.com/questions/32843/… –  mghandi Apr 13 '11 at 20:38

Your Answer

 
discard

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.