Una matriz de expresiones regulares de m renglones y n columnas es un arreglo
tal que
.
Denotemos por
a la clase de matrices de expresiones regulares de m renglones y n columnas.
Si
su suma es la matriz
tal que
.
Si
y
el producto por un escalar por la izquierda
es la matriz
tal que
.
Simétricamente, el producto por la derecha
es la matriz
tal que
.
También de manera convencional, definimos el producto de dos matrices
y
como la matriz
tal que
.
Con estas operaciones las matrices cuadradas
poseen una estructura de semianillo (lo único que les falta para ser un anillo son inversos aditivos) no-conmutativo. La unidad aditiva es la matriz cero
y la unidad multiplicativa es la matriz identidad
.
Las operaciones matriciales son congruentes con ``particiones por bloques'', es decir, si se parte a dos matrices
como
donde bloques con mismos índices ij son de mismos tamaños, entonces
Dadas dos matrices
,
diremos que
si
.
Diremos también que una matriz
posee la CPV si
.
Ahora la operación ``estrella'' de matrices ha de generalizar la operación ``estrella'' de las expresiones regulares. Consecuentemente, se ha de definir de manera que
se satisfaga la ecuación
,
y
la solución de la ecuación
sea
,
siempre que
no posea la CPV.
Para esto, supongamos primero que ya se haya construido tal operación ``estrella''. Denotemos por
a la ``estrella'' de
.
Si consideramos particiones de tamaños similares
Ahora bien, de la identidad
(X+Y)*=(X*Y)*X* obtenemos la expresión equivalente
También de la identidad
(XY)*X=X(YX)* obtenemos
y por tanto,
(37)
Las ecuaciones (4.25) y (4.26) dan sendos métodos de cálculo de la matriz
.
Así, por ejemplo, de acuerdo con la ecuación (4.26), dada una matriz
y una partición de ella por bloques
entonces al hacer
hemos de tener que
Los cálculos anteriores pueden realizarse para cualquier partición de la matriz
por bloques. Sin embargo, diversas particiones serán más eficientes respecto a otras.
Como un primer ejemplo, supongamos que formamos bloques ``quitando'' el último renglón y la última columna. En otras palabras, supongamos
Sea T(n) el número de potencias ``estrellas'' escalares necesarias para calcular la potencia ``estrella'' de
.
Siguiendo las relaciones anteriores, necesitamos calcular 2 potencias ``estrellas'' de matrices
,
las de las matrices
y
,
y dos de matrices ,
las de las matrices
y
.
Por tanto,
Al resolver la recurrencia anterior obtenemos como solución
y consecuentemente
T(n)=O(2n).
Ahora, como un segundo ejemplo, supongamos que n=2k es una potencia de 2. En este caso, de acuerdo con las relaciones anteriores, para calcular la potencia ``estrella'' de
hay que calcular 4 potencias ``estrellas'' de matrices
.
Por tanto,
Esta vez, la recurrencia tiene solución
Ya que
vemos que es mucho más conveniente introducir particiones por ``medias'' matrices que quitando un renglón y una columna a la vez.
Como en el caso ``escalar'' tenemos que se cumple el siguiente
Lema 3.2
Si
y
entonces la mínima solución de la ecuación
es
.
Más aún, si
no posee la CPV entonces la solución mínima es la única solución.
Ejemplo:
Para una matriz
,
se tiene, aplicando el algoritmo de cálculo de la operación ``estrella'' en matrices, que
(38)
Ahora bien para una matriz
,
es necesario reiterar desde un segundo nivel el procedimiento descrito de la operación ``estrella'' en matrices. En este caso tendremos que