Propiedades Matriciales

El diagrama de de Bruijn es la construcción fundamental que representa la regla de evolución y por lo tanto el comportamiento de un autómata celular. Aplicando conceptos básicos de teoría de gráficas, existe una matriz binaria para cada estado o tipo de liga. El diagrama de de Bruijn tiene una representación matricial para cada tipo de arista en donde los índices representan los nodos y los elementos las ligas que existen entre estos. Si un nodo está conectado con otro con ese tipo de arista, el elemento definido por estos índices será un $1$, en otro caso será un $0$; a esta matriz se le denominará la matriz de conectividad del tipo de liga o estado correspondiente.

Para una secuencia de estados dada, tomemos la matriz de conectividad de cada estado y multipliquemos éstas siguiendo el orden que dicta dicha secuencia, el resultado de este proceso dará lo siguiente:

• La suma de los elementos matriciales indica cuantas posibles formas tenemos de producir dicha secuencia.
• El número de renglones con elementos no todos $0$ indica cuantas formas tenemos de iniciar la secuencia.
• Los renglones con elementos no todos $0$ señalan de cuales nodos surge esta secuencia.
• El número de columnas con elementos no todos $0$ indica cuantas formas existen de terminar dicha secuencia.
• Las columnas con elementos no todos $0$ indican en cuales nodos finaliza dicha secuencia.

Con estas simples observaciones tenemos que en un autómata reversibles, la matriz de conectividad de toda secuencia debe cumplir que la suma de sus elementos sea igual a $k^{2r}$, la suma de sus renglones diferentes a $0$ debe ser $L$ y la suma de sus columnas con la misma propiedad debe ser $R$. En otras palabras, las representación matricial, nos manifiesta numéricamente la multiplicidad uniforme y los índices $L$ y $R$, además de, presentarnos cuales son los elementos que conforman los extremos de los ancestros, o sea, los conjuntos ${\cal R}_{i}$ y ${\cal L}_{i}$ de dicha secuencia, con lo que se puede obtener con este proceso los nodos de los diagramas de Welch derecho e izquierdo; un análisis más detallado en este aspecto puede encontrarse en [Seck 98].

Al trabajar con matrices es una tentación aplicar la teoría de algebra matricial para obtener más información sobre el comportamiento de las mismas. La obtención de eigenvalores y eigenvectores indican, para los primeros, la proporción de proliferación de los elementos al elevar la matriz a potencias sucesivas; del mismo modo, viendo la matriz como una transformación en el espacio los eigenvectores nos indican sobre que ejes y en que medida se presentarán dichas transformaciones.

Trabajando con las matrices de conectividad del diagrama de de Bruijn, observaremos que para cada estado, su matriz de conectividad tendrá un único eigenvalor igual con $1$, en otras palabras, los ancestros no proliferarán m's allá de como están definidos al principio, y los eigenvectores representarán de cuantos y cuales nodos en el diagrama de de Bruijn partirán las rutas que comienzen en dicho estado. Si quisieramos conocer lo contrario, es decir, de cuantos y a cuales nodos llegarán las rutas que terminen en dicho estado, solo basta con transponer la matriz y obtener el eigenvector correspondiente, los elementos del mismo nos mostrarán esa información.

En síntesis, el que las matrices de conectividad tengan un único eigenvalor igual con $1$ es señal que el número de ancestros se mantendrá; si esto es igual para todas las matrices de conectividad posibles es debido a la multiplicidad uniforme. Por medio de los eigenvectores podemos reconstruir a las matrices de conectividad, multiplicando los eigenvectores renglón con los eigenvectores columna, formando así todas las posibles instancias de las matrices de conectividad.