Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas 39 Jose Arturo Barreto. Master of Arts.

The University of Texas at Austin. Pgina Web: [Link] LGEBRA LINEAL EN CONTEXTO JOS ARTURO BARRETO GUTIRREZ

CAPITULO 2. MATRICES PARTICIONADAS. DESCOMPOSICION LU. OBJETIVOS: Al terminar este captulo el estudiante estar en capacidad de: 1. Aplicar el concepto de matriz particionada para reducir un problema en varios problemas, relacionados, de menor dimensin. 2. Descomponer una matriz A en un producto LU o PTLU, donde P es una matriz de permutacin. 3. Utilizar la descomposicin LU en diferentes contextos MATRICES ELEMENTALES.

40 Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] 2.1. PARTICION DE UNA MATRIZ. OPERACIONES ENTRE MATRICES PARTICIONADAS. DEFINICION: Dada una matriz A de dimensin mxn, se dice que la matriz C es una SUBMATRIZ de A si C se puede obtener de A al suprimir (en A) algunas filas y (o) columnas. Se considera que A es una submatriz de si misma. (1.2) EJEMPLO: Si en 1 A= 5 1 2 6 1 3 7 1 4 8 1

eliminamos la segunda columna, obtenemos la submatriz 1 C1 = 5 3 7 1 Otras submatrices son: 1 C2 = 5 6 8 2 4 1 4 8 1

(obtenida de A al eliminar la tercera fila y la tercera columna) C3 = (1 3 4)

(obtenida de A al eliminar las filas segunda y tercera y la segunda columna). Podemos considerar a la matriz A 1 2 A = 3 7 4 3 8 2 5 0 4 1 5 6 9 0 7 9 6 8

PARTICIONADA por bloques como 1 5 9 l 7 6 2 6 0 l 9 8 A = 3 7 3 l 2 0 ----------------------------l--------------4 8 5 l 4 1

Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas 41 Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] O sea que A11 A = A21 En donde 1 A11 = 2 5 6 9 0 3 , 7 A12 = 2 A22 6 9 0 8 , A21 = ( 4 8 5), A12

3 7 A22 =

(4 1) 3 -1 2 4 3 4 l 1 B = l -3 l 6 -2 -5 l 1 4 ----------------------------l------------------3 1 2 l1 2 5 2

Son submatrices de A Si

es decir, la matriz B ha sido particionada como B11 B = B21 Entonces A11 + B11 (1.2) A+B = A21 + B21 En consecuencia : Si las matrices A y B han sido particionadas como A11 (1.3) A = A21 Am1 Y B11 (1.4) B = B21 Bm1 B12. B22. Bm2. . . . . . . B1n B2n Bmn A12. A22. Am2. . . . . . . A1n A2n Amn A22 + B22 A12 + B12 B22 B12

En donde cada suma de matrices Ai j + Bi j

42 Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] Est definida, podemos afirmar que A11 (1.5) A+B = + B11 A21 A12 + B12 . . Am1 . . + Bm1 Am2 . .+ A1n .+ + B1n A2n + B2n . . . . + Bmn

+ B21

A22 + B22 . . . . . . . + Bm2 . . .+

Amn

Las matrices de 1.3 y 1.4 como matrices particionadas son de dimensin mxn. Diremos que la DIMENSION PARTICIONADA de A y B es mxn. La dimensin de las matrices A y B de 1.3 y 1.4 es mayor que mxn a no ser que las submatrices Ai j sean de orden 1 (es decir a no ser que las matrices esten PARTICIONADAS EN SUS ELEMENTOS). En 1.5 hemos expresado en smbolos el siguiente teorema: TEOREMA : Dos matrices de igual dimensin particionadas se pueden sumar (restar) como si las submatrices fuesen elementos ordinarios, siempre y cuando las matrices estn particionadas de tal manera que sea posible efectuar las adiciones (sustracciones) de las submatrices. Si la matriz A est particionada como 1 A = l 5 l 3 4 l 6 ------------- --l------7 8 l 9 A11 (1.7) A = A21 A22 A12 2

O sea

Puede verificarse que para todo nmero real (1.8) A = 2 3 7 5 4 8 6 9 A11 = A12 A21 A22

La igualdad (1.8) es un caso particular del siguiente teorema: (1.9). TEOREMA: Si la matriz A est particionada como A11 A = A21 Am1 entonces, para todo nmero real A12. A22. Am2. . . . . . . A1n A2n Amn

Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas 43 Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] y A11 A12. . . A1n A = . Am1 A21 A22 . . Am2. . . . . Amn A2n .

Adems de los teoremas 1.6 y 1.9, el siguiente teorema es vlido para el caso de matrices particionadas. (1.10) Si las matrices A11 A = A21 Am1 y B = B11 B21 . Bn1 A12. A22. Am2. B12. B22. . Bn2. . . Bnn . . . . . . . . . . A1n A2n Amn B1n B2n .

Son de matrices de dimensiones particionadas mxn y nxk respectivamente y el producto AB est definido entonces: C11 AB = C21 . C12 . C22 . . Cm1 . . . Cm2 . . . Cmk . C1k .C2k .

En donde cada submatriz Cij se puede calcular como (1.11) Ci j = Ai1 B1j + Ai2 B2j +... + Ain Bnj

siempre y cuando todos los productos y sumas de 1.11 estn definidos. En consecuencia el producto de matrices con las condiciones exigidas por el teorema 1.10 se puede efectuar entre matrices particionadas siguiendo la regla usual de su multiplicacin y considerando a las submatrices como elementos. (1.12) EJEMPLO: Sea A11 A= A21 Si todos lo productos estn definidos A11 B11 + A12 B21 + A13 B31 (1.13) AB= A21 B11 + A22 B21 + A23 B31 A21 B12 + A22 B22 + A23 B32 Ntese que la dimensin particionada de A es 2x3, la de B es 3x2 y en consecuencia la de AB es de 2x2 como se puede constatar en 1.13. A11 B12 + A12 B22 + A13 B32 A22 A23 A12 A13 Y B21 B = B11 B22 B12 B31 B32

44 Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link]

Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas 45 Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] (1.14) EJEMPLO: Sean 2 (1.15) l---------------------------1 Y -1 4 ----------2 1 -1 (1.16) B = 5 1 0 1 ----------3 2 -1 l 1 -1 l 0 0 0 A = l 0 l 1 l 4 -1 7 l l 0 0 l -2 0 -----l--------------------0

Matrices particionadas como lo sealan las lneas punteadas en 1.15 y 1.16. Entonces, como las dimensiones de A y B son 3x6 y 6x2, respectivamente, el producto AB est definido y es de dimensin 3x2. Se puede verificar directamente que: 17 (1.17) AB = 2 11 -11 4 -5

Como las dimensiones particionadas de A y B son 2x3 y 3x1 respectivamente y todos los productos y sumas necesarios de submatrices estn definidos entonces 2 3 -1 1 -1 (1.18) AB = ( 1) 2 -1 1 0 -1 Efectuando los productos de submatrices en 1.18 tenemos que -2 (1.19) AB = -1 8 4 + -1 + 19 4 3 3 -10 0 -9 ( -1 4) + (1 4 + 0 0 2 -1 1 1 -1 ) + -2 0 3 5 0 3 0) 1 2 0 0 0 2 1 4 -1 7 5

(0

46 Captulo 2 Particin de una matriz. Operaciones entre matrices particionadas Jose Arturo Barreto. Master of Arts. The University of Texas at Austin. Pgina Web: [Link] 17 = 11

-11 -5 ----------------2 4

Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] El cual es el resultado consignado previamente en 1.17. (1.20) EJEMPLO: Las matrices A = 1 0 -----------2 1 1 Y B = -1 1 l l 2 l 1 1

47

Particionadas como se indica por las lneas punteadas, tienen dimensiones particionadas 2x1 y 1x2 respectivamente, por lo tanto el producto particionado se puede efectuar siempre las sumas y productos de las submatrices estn definidos. Puede verificarse que 1 (1 AB = 1 (2 1) -1 2 1 = 1 1 4 1 3 1 (2 1) 1 1 0) -1 2 1 (1 0) 1 1

1 1 | 1 ------------ ----|------1 4 | 3

Efectuando directamente el producto vemos que 1 AB = 2 1 -1 2 0 1 1 1 = 1 1 1 1 4 1 3

Conocer los resultados sobre matrices particionadas de esta seccin es de utilidad tanto terica como prctica como lo muestra los dos ejemplos siguientes: 2.2.- Aplicaciones (2.1) EJEMPLO: Suponga que una matriz T ha sido particionada como A (2.2) T = 0 C B

En donde A y C son matrices cuadradas de orden l y m respectivamente (T ser por lo tanto de dimensin l + m). Si A y C son no singulares entonces T es no singular ya que se puede probar que A- 1 (2.3) Puesto que T- 1 = A B -A- 1 BC 0 A- 1
-1

C-1

-A- 1 BC - 1

48 Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] = 0 C B.0 0 C
-1

AA - 1 +

-AA-1 BC-1

+ =

BC-1 CC-1

0.A - 1 + C.0 I 0 (2.4) 0 = I I

0.(-A-1 BC-1) +

EJEMPLO: Si deseamos hallar la matriz inversa de una matriz cuadrada T que se puede particionar como en 2.2, en donde las matrices A y C son matrices cuadradas no singulares, procederamos tal como lo mostraremos a continuacin.

Sea por ejemplo: 1 T = l 5 l 3 4 l 7 ---------------l-------0 0 l 8 2 A = 0 C B

Las matrices A y C son de orden 2 y 1 respectivamente. A es no singular ya que: -2 A-1 = 3/2 (Verifique que AA-1 = I ) -1/2 1

Como C = ( 8 ) , entonces C es no singular ya que C-1 Como 2 -A BC

( 1/8 ) -1 5 (1/8) -3/2 1/2 3/8 = -1/2 , 7

Concluimos a partir de 2.3 que -2 l T-1 = 3/2 0 -1/2 l-1/2 ------------------l--------0 l 1/8 1 l 3/8

Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] Puede verificarse por multiplicacin directa que T T-1 = I

49

La particin de matrices tiene singular importancia en el desarrollo de algoritmos numricos, como lo trataremos de justificar a continuacin. Como veremos ms adelante, un sistema de ecuaciones tal como 2x + 3y + z + w = 1 4x + y - z + w = 0 y + 2w

(*)

se denomina un sistema de ecuaciones lineales simultneas: no hay trminos mixtos en xy, xz, yz, xyz, etc., y cada variable est elevada a la primera potencia. La matriz A = 2 3 1 1

4 1 -1 1 0 1 0 2 formada por los coeficientes de las variables x, y ,z w, en su orden, se denomina la matriz de los coeficientes del sistema. El sistema de ecuaciones (*) se expresa matricialmente como: AX = B, en donde X = x y z w 1 0 B = -1 0

Es el caso de un sistema tal como x + 2y =3 2x - y el cual podra escribirse como 2 2 -1 es decir, en la forma AX = B en donde 2 x A= 2 X =y -1 Como A es no singular, entonces X = A-1 B 3 B = 1 x y = 3 1

50 Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] Parece sencillo por lo tanto resolver el sistema de ecuaciones lineales 2x + 3y + z + w = 1 4x + y - z + w = 0 y + 2w = -1 2 3 1 AX = 1 B 3 A= 1

A partir de en donde

1 4 X = A-1 -1 1 1 por medio de la igualdad 0 B 1 0 2 1 0 1 0 -1 Para ello deberamos proceder a calcular A . Como veremos mas adelante, el clculo de A-1 para matrices de orden n > 2 es generalmente arduo. Mas en algunos casos, como en el caso de las matrices dispersas que se presentan en muchas aplicaciones, los elementos diferentes de 0, se encuentran o se pueden agrupar en bloques, reduciendo el problema a varios subproblemas de menor dimensin, con paso de datos como se ejemplificar a continuacin. Si el paso de datos es mnimo, muchos subproblemas se podrn resolver sin esperar el paso de datos de otros subproblemas. Los algoritmos actuales pretenden utilizar esta metodologa utilizando computadores paralelos o sistemas en paralelo minimizando, por supuesto, el paso de datos. Ejemplificaremos esto con un ejemplo sencillo. Ejemplo utilizando matrices particionadas El sistema de ecuaciones lineales 2y + 3z + 2w = 1 x+ 2x - y + 4z + w= 0 2z = -1 se puede particionar como A11 0 A12 A22 x y -z w 3w = 0 1 0 --1 = 0

La matriz A es triangular por bloques. En el cual 1 A11 = 2 -1 2 3 4 2 1 2 0 A22 = 0 3

A12 =

Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link]

51

Lo cual nos lleva a:

x y A11

z 1 + A12 0 w z -1 A22 w 0

O de forma equivalente 11 X + A12 Z = A B1 A22 Z

52 Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] En donde -1 B2 = 0 w El sistema matricial de ecuaciones enmarcado en gris, es un sistema triangular superior por bloques. x X= y z Z =w 1 B1 = 0 Solucionando las igualdades, utilizando sustitucin regresiva y lgebra matricial, llegamos a: (*) Z = A22-1 B2 (**) X = A11-1 ( B1 A12 Z ) La ecuacin (**), espera el valor de Z que se calcular previamente en (*). Si este mtodo, se aplicara en un computador (siendo las matrices de orden mayor), habra ahorro de memoria si una ecuacin se efectuara antes que la otra, mas sin embargo el tiempo de ejecucin no se reducira notablemente ya que (**) tendra que esperar los resultados de (*). An as, si el sistema se resolviera en paralelo, podran adelantarse las operacines A11-1 B1 y A11-1 A12, aprovechndose el tiempo mientras llega el valor de Z que proporcionar (*). A partir de este ejemplo se puede intuir la importancia de la teora que estamos estudiando ya que pese a su sencillez tiene grandes aplicaciones prcticas que se conocern en cursos profesionales. Adems nos muestra que la teora es fundamental en el momento de buscar soluciones a problemas prcticos y por lo tanto amerita cierto nivel de comprensin en este nivel. La matemtica es quizs an, como se le ha llamado durante siglos, la reina de las ciencias. La cuidadosa solucin de las ecuaciones matriciales enmarcadas arriba nos arrojar los valores x = 13/10, y = 3/5, z = -1/2, w = 0.

A partir de (*) y (**), vemos que la siguiente igualdad de matrices particionadas es vlida, reemplazando en (**) Z por A22-1 B2 (de *): A11-1 A11-1 A12 X Z = A22-1 0 B1 A22-1 B2

A11-1 A11-1 A12 A22-1

No es de extraar que la matriz 0

A22-1

sea precisamente la matriz inversa (verifquelo) de la matriz particionada A = A11 A12

0 A presentada al iniciar este ejemplo 22 sugiriendo que la solucin pudo plantearse utilizando la igualdad

Captulo 2 Aplicaciones Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link]

53

X = A-1 B (como es usual en este texto, hemos sobrecargado, utilizando un trmino muy utilizado en la programacin orientada a objetos, el trmino X, ya que ahora se refiere a una matriz (vector) de dimensin 4x1 y no es la misma X de dimensin 2x1 utilizada un poco antes. Esta no es a nuestro juicio una mala prctica y no debe marear a nuestros lectores).

54 Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] La respuesta a la que se llega utilizando la matriz inversa anterior es la misma x = 13/10, y = 3/5, z = -1/2, w = 0.

a la cual se llegara por cualquier otro mtodo sin utilizar el lgebra de matrices particionadas. 2.3.- Ejercicios Propuestos 1). Dadas 4 A Y 0 -1 l 2 1 I 6 ------------ ---l------B = 5 I -3 4 I -1 2 Efecte AB. a) b) 2) Multiplicando sin utilizar las particiones indicadas . Utilizar las particiones. Muestre que si A es la matriz particionada AT11 A11 A = A21 A 3)
T 22

= 2

l -2 l -5 l 6 l

1 3 3

4 -1 ,

2 I

l 1

-1

, I

AT21 = AT12

A12 , A22 entonces AT

Muestre que si A1 , A2 y A3 son matrices no singulares, entonces A1 0 0 0 A2 0 0 0 A3 -1 = A-1 0 0 0 A2-1 0 0 0 A3-1

Halle la matriz inversa de la matriz, utilizando la particin sugerida. 1 l 0 0 l 3 1 l 0 0 ---------------l------------------0 0 l 4 5 l 0 0 l 6 2 2

Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] 4) Una matriz cuadrada T es TRIANGULAR t11 0 0 . . 0 t12 t22 0 . . 0 t13 t23 . . . t1n . . , t2n SUPERIOR si

55

t33 . . . t3n . . . . . . 0 . . . tnn

Es decir, si tij = 0 para i > j. Sea T una matriz cuadrada triangular superior. i) ii) Si T es no singular, entonces tii matriz triangular superior. 0 (i = 1,2....n) y adems T-1 es una

Demuestre que si ti i 0 (i = 1,2,....n), entonces T es no singular. ****************************** (Ayuda: Si T es no singular existe una matriz X11 X21 X31 X = X41 . . . Xn1 X42 . . . Xn2 X43 . . . Xn3 X44 . . . Xn4 . . . . . . . . .Xnn X4n X12 X22 X32 X13 X23 X33 X14 X24 X34 . . . . . . .X1n .X2n .X3n

Tal que (1) TX = I

A partir de (1) muestre que tnn xnn Adems que tnn xn , n - 1

Y en consecuencia que tnn

= = =

0 0 0

xn ,

n-2

. . tnn xn 1 y concluya que xn , n - 1 = xn , n - 2 =. . .= xn 1 = 0

56 Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] es decir X11 X21 X31 X = X41 . . . 0 X42 . . . 0 X43 . . . 0 X44 . . . 0 . . . . . . Xnn X4n X12 X22 X32 X13 X23 X33 X14 X24 X34 . . . . . . . . . X1n X2n X3n

Utilizando argumentos similares pruebe ahora que tn - 1 , n - 1 Y xn - 1 , n - 2 = xn - 1 , n - 3 = . . . = xn - 1 , 1 = 0 Continuando de ste modo concluira i). 5) Teniendo como base el hecho que toda matriz triangular de orden n se puede expresar en la forma Tn - 1 T = 0 En donde Tn - 1 tnn es una matriz triangular de orden n 1, t1n y B = t2n . . . tn - 1 , n , demuestre que Bn - 1 0

n-1

i) ii)

T es no singular si y slo si Tn - 1 es no singular y tnn Si T es no singular T-1n - 1 T

-Tn - 1n - 1 t

Bn - 1 tnn-1
-1 nn

= 0

iii)

Ntese que T-1n - 1 en la matriz anterior es una matriz triangular de orden n 1 y a su vez T T-1n - 1 = 0 T-1n - 1 ,
n-1 -1

n-2

-T

-1 n-2

Bn - 2 t

-1

n-1

n-1

Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link]

57

En donde t1 , n - 1 t1 , n - 1 . . . t n - 2, n - 1 Por lo tanto la frmula de recurrencia (*) T-11 = . . . -1 T k+1= t-111 T 0 con t1,k+1 t2 , k + 1 Bk = . tk es tal que T-1n = T-1 6) i) Utilizando la frmula de recurrencia ( * ) del problema 5 calcule T-1 para 1 0 T = 0 0 ii) Utilizando la particin 1 T = -1 l 2 1 l 0 2 l 1 0 ---------------l-----------------0 0 l 3 0 l 0 0 l 0 1 0 0 3 0 0 1 -1 2 2 1 1 0 .
,k+1 -1

Bn - 2

-T

-1 k

Bk t

-1

k+1,k+1

t-1k + 1 , k + 1

calcule T . 1

-1

de nuevo, calculando primero -1

3 y

-1

58 Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] 0 2 0 1

7. Demuestre que dada la matriz A B T = 0 C 0 Donde A y C son matrices cuadradas no singulares, entonces: A T 1 2 Y si A T = B C y A y C son matrices cuadradas no singulares, entonces: 0
-1 -1

- A -1B C C
-1

-1

= 0

A T Adems, si
-1

-1

0
-1

= - A -1B C B T= A C C C
-1

y B son matrices no singulares, entonces, T es una matriz no singular y - A 1C B -1 T

A 1 0

= B 1

3 8. Utilizando los resultados del problema 7, halle las matrices inversas (cuando existan) de las siguientes matrices: 1 0 0 0 0 0 2 0 , 0 -1/2 1 0 0 k 0 1 0 0 3 1 1 , 4 2 1 2 0 0 0 1 3 0 0 0 , 0 0 2 0 0 0 0 0 4 0 0 0 1 1 1 , 0 0 0 1 2 0 0 1 1 0 0 1 0 2 0 1

k 0 1 k 0 1

0 0 k1 0 k2 0 k3 0 0

0 1 0 , 1 0 0 0 0 1

9. Suponga que una matriz cuadrada P ha sido particionada como I P = C B 0 en donde I es la matriz idntica.

Captulo 2 Ejercicios propuestos Jos Arturo Barreto Gutirrez Master of Arts. The University of Texas at Austin. Pgina Web: [Link] Demuestre que: I P =
2

59

C + BC B2 10. Suponga que una matriz no singular ha sido particionada como: 0 A= Q I P en donde P y Q son matrices cuadradas del mismo orden.

Demuestre que en este caso P y Q son matrices no singulares y que: - (PQ) A 1 = 11. 1 0 0 0 12. P 1 0 Halle la matriz inversa de las siguientes matrices: 1 2 0 0 1 1 1 0 1 2 3 1 1 1 1 1 0 2 1 2 0 0 1 3 0 0 0 1
1

Q 1

Resuelva el sistema de ecuaciones lineales

utilizando las matrices particionadas 1 2 3 2 A11 = 2 -1 A12 = 4 1

A22 = 0 3

Plantee el sistema en la forma matricial

A11 X + A12 Z = B1 A22 Z = B2 i) Resuelva el problema a partir de la solucin del sistema con matrices particionadas anterior, por sustitucin regresiva. ii) Resuelvalo utilizando el sistema de ecuaciones AX = B, por medio de X = A-1 B, en donde A11-1 A11-1 A12 A11 A= 0 A12 A22 y A-1 = A22-1 0

A22-1