descomposición propia de una matriz interesante

Question

Permite definir:

$U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ el conjunto de todos los diferentes secuencias binarias de longitud $L$.

$V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ el conjunto de todos los diferentes boquiabierto secuencias binarias con $k$ conocido bits y $L-k$ lagunas.

$A_{M*N}=[a_{i,j}]$ es una matriz binaria definida de la siguiente manera:

$$a_{i,j} = \left\{\begin{matrix} 1 & \text{if } v_i \text{ matches } u_j \\ 0 & \text{otherwise } \end{de la matriz}\right.$$

ahora, la pregunta es: ¿cuáles son los autovectores y autovalores de la matriz $S_{M*M}=AA^{T}$?

Aquí es un ejemplo para $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}$$

Para el caso especial $k=1$, se ha resuelto previamente por joriki y la solución se puede encontrar aquí. Ver la misma referencia para un gráfico de la analogía de la matriz $S$.

Además, se ha demostrado aquí por joriki que: $$\text{rank}(AA^{T})=\text{rank}(A)=\sum_{m=0}^k\left({L\atop m}\right)\;\;$$ Como para los valores propios, los valores numéricos sugieren que $AA^{T}$ $\binom{L}{m}$ autovalores igual a $\binom{L-m}{k-m}2^{g}, m=0,..,k$ donde $g=L-k$ es el número de huecos.

cualquier comentario o sugerencia se agradece.

$^{*}$ aquí los puntos denotan carencias. una brecha que puede tomar cualquier valor, y cada uno boquiabierto secuencia con $k$ conocido bits y $(L−K)$ vacíos en $V$, coincide exactamente con a $2^{L−k}$ de las secuencias en la U, por lo tanto la suma de los elementos de cada fila de a$A$$2^{L−k}$.

Answer 1

Los vectores propios correspondientes a la no-cero autovalores se pueden enumerar de la siguiente manera. Para cada una de las $m=0,1,...,k$, pick $m$ las posiciones de los bits de la total $L$. Esto se puede hacer en $\binom {L} {m}$ maneras. Definir el vector x, con $i^{th}$ elemento $x_i$, dado por

$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{casos} $

Este es un autovector de a $S = AA^T$ con autovalor $\binom {L-m}{k-m}*2^{L-k}$. Para mostrar esto, vemos por primera vez que $S_{ij}$ ($ij^{th}$ la entrada en $S=AA^T$) es el número de elementos en $U$ que coincidan $v_i$$v_j$. A partir de la construcción de la $x$, podemos hacer dos observaciones. En primer lugar, si $x_i \neq 0$, $x_j = x_i$ siempre $v_i$ tiene un común coincide con $v_j$, es decir, whenver $S_{ij}$ es distinto de cero. En segundo lugar, si $x_i = 0$, entonces para cada a$j_1$$S_{ij_1} \neq 0$$x_{j_1} \neq 0$, podemos encontrar un único $j_2$ tal que $S_{ij_1} = S_{ij_2}$$x_{j_1} = - x_{j_2}$. Esto es porque, $x_i = 0$ implica que hay una brecha entre el $m$ bits en $v_i$. Para alternar un poco en $v_{j_1}$ da $v_{j_2}$$S_{ij_1} = S_{ij_2}$$x_{j_1} = -x_{j_2}$.

De ello se deduce a partir de la segunda observación anterior de que si $x_i = 0$, $i^{th}$ entrada en $Sx$ es 0. Y a partir de la primera observación, si $x_i = 1$, $i^{th}$ entrada en $Sx$ es el número de elementos en $U$ que coincidan $v_i$$v_j$, sumando todos los $j$$x_j = 1$. Este es el mismo que el número de $v_j$, lo que coincide $u$, sumando todos los $2^{L-k}$ diferentes $u$, lo que coincide $v_i$. Este número puede ser demostrado ser $\binom{L-m}{k-m}* 2^{L-k}$. Resultado Similar se puede demostrar a $x_i = -1$ de los casos. Por lo $x$ descrito anteriormente es un autovector de a $S$ con autovalor $\binom{L-m}{k-m}* 2^{L-k}$. Como podríamos optar $m$ bits en $\binom{L}{m}$ formas, obtenemos $\binom{L}{m}$ vectores con este autovalor. Estos vectores pueden ser mostrados para ser mutuamente ortogonales, por lo tanto, son linealmente independientes.

Con $m$ variación de$0$$k$, obtenemos como muchos vectores propios como el rango de la matriz, cada uno con un valor distinto de cero autovalor. Así que esto le da a todos los vectores propios con los no-cero autovalores.