AlgebraLineal Kolman Bernard Hil David R

Sec. 2.2 Teoría de gráficas 127 MODELOS EN SOCIOLOGÍA Y COMUNICACIONES Suponga que tenemos n individuos P1, P2, . . . , Pn, algunos de los cuales tienen rela- ción entre sí. Daremos por sentado que ninguno de ellos tiene relación consigo mismo. Algunos ejemplos de estas relaciones son: 1. Pi tiene acceso a Pj. En este caso, puede suceder o no que si Pi tiene acceso a Pj, también Pj tenga acceso a Pi. Por ejemplo, muchos teléfonos de emergencia en las autopistas permiten que el viajero llame a una estación de auxilio cercana, pero no que la estación se comunique con el viajero. Este modelo se representa mediante una digráfica G como sigue. Sean P1, P2, . . . , Pn los vértices de G; tracemos una arista dirigida de Pi a Pj si Pi tiene acceso a Pj. Es importante observar que esta relación no necesariamente es transitiva. Es decir, Pi puede tener acceso a Pj y Pj puede te- ner acceso a Pk, pero no necesariamente Pi tiene acceso a Pk. 2. Pi influye en Pj. Esta situación es idéntica a la del punto 1: si Pi influye en Pj, Pj po- dría influir en Pi, pero no necesariamente. 3. Para cada par de individuos Pi, Pj, Pi domina a Pj o Pj domina a Pi, pero no es po- sible que ambos sean dominantes. La gráfica que representa esta situación es la di- gráfica completa con n vértices. Tales gráficas suelen denominarse gráficas dirigidas (o digráficas) de dominancia. EJEMPLO 5 Suponga que seis individuos se han reunido en sesiones de terapia de grupo durante mu- cho tiempo, y el moderador, que no es parte del grupo, ha trazado la digráfica G de la P3 figura 2.7 para describir las relaciones de influencia entre ellos. La matriz de adyacen- cia de G es G P2 P1 ⎡ P1 P2 P3 P4 P5 P6 ⎤ P1 0 0 0 0 1 0 P5 P6 P2 ⎢⎢⎢⎣⎢⎢ 0 0 0 0 1 0 ⎦⎥⎥⎥⎥⎥. P3 1 1 0 0 1 0 A(G) = P4 0 1 0 0 1 0 P5 0 0 0 0 0 0 P4 P6 0 1 0 1 0 0 Figura 2.7 ᭡ Al observar las filas de A(G), vemos que P3 tiene tres unos (1) en su fila, de modo que P3 influye en tres personas (más que cualquier otro individuo). En consecuencia, P3 sería declarado líder del grupo. Por otro lado, P5 no influye en persona alguna del grupo. ■ EJEMPLO 6 Considere una red de comunicación cuya digráfica G se muestra en la figura 2.8. La ma- triz de adyacencia de G es P3 G P1 P2 ⎡ P1 P2 P3 P4 P5 P6 ⎤ P1 ⎢⎢⎢⎢⎣⎢⎢⎢⎢ 0 0 0 0 1 0 ⎦⎥⎥⎥⎥⎥⎥⎥⎥. P2 0 0 0 0 1 P5 P6 P3 1 1 0 0 1 1 P4 0 1 0 0 1 0 Figura 2.8 ᭡ A(G) = P5 0 1 0 0 0 1 1 P4 P6 1 0 1 0 0 0

128 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) Aunque la relación “Pi tiene acceso a Pj” no es necesariamente transitiva, podemos hablar de un acceso en dos etapas. Decimos que Pi tiene acceso en dos etapas a Pk si encontramos un individuo Pj tal que Pi tiene acceso a Pj y Pj tiene acceso a Pk. De ma- nera similar, Pi tiene acceso en r etapas a Pk si podemos determinar r − 1 individuos Pj1 , . . . , Pjr−1 , tales que Pi tiene acceso a Pj1 , Pj1 tiene acceso a Pj2 , . . . , Pjr−2 tie- ne acceso a Pjr 1, y Pjr 1 tiene acceso a Pk. Algunos de los r + 1 individuos Pi , Pj1 , . . . , Pjr−1 , Pk pueden ser iguales. A partir de lo anterior es posible establecer el siguiente teorema, cuya demostra- ción omitiremos. TEOREMA 2.1 Sea A(G) la matriz de adyacencia de una digráfica G, y sea Br la r-ésima potencia de A(G): [ A(G)]r = Br = [ bi(rj ) ]. Entonces, el elemento i, j de Br, bi(rj ) es el número de formas en que Pi tiene acceso a Pj en r etapas. ■ La suma de los elementos de la j-ésima columna de [A(G)]r proporciona el núme- ro de formas en que Pj puede ser alcanzado por los demás individuos en r etapas. Si hacemos A(G) + [A(G)]2 + · · · + [A(G)]r = C = [cij], (1) entonces cij es el número de formas en que Pi tiene acceso a Pj en una, dos, . . . , o r etapas. De manera similar, podemos hablar de dominio en r etapas, de influencia en r eta- pas, y así sucesivamente. También podemos utilizar este modelo para estudiar la propa- gación de un rumor. Así, cij en (1) es el número de formas en que Pi ha propagado el rumor hasta Pj en una, dos, . . . , o r etapas. En la relación de influencia, la influencia en r etapas muestra el efecto de la influencia indirecta. EJEMPLO 7 Si G es la digráfica de la figura 2.8, encontramos que P1 ⎡ P1 P2 P3 P4 P5 P6 ⎤ 0 1 0 0 0 1 [ A(G)]2 = P2 ⎣⎢⎢⎢⎢⎢ 1 1 1 0 0 1 ⎥⎥⎥⎥⎦⎥ P3 0 1 0 0 2 2 P4 1 1 1 0 1 2 P5 1 0 1 0 1 1 P6 1 1 0 0 2 0 y P1 ⎡ P1 P2 P3 P4 P5 P6 ⎤ 0 1 0 0 1 1 A(G) + [ A(G)]2 = C = P2 ⎢⎢⎢⎢⎣⎢ 1 1 1 0 1 2 ⎥⎦⎥⎥⎥⎥. P3 1 2 0 0 3 2 P4 1 2 1 0 2 3 P5 1 1 1 0 1 2 P6 2 1 1 0 2 0 Como c35 = 3, hay tres formas en que P3 tiene acceso a P5 en una o dos etapas: P3 →P5, P3 → P2 → P5 y P3 → P1 → P5. ■

Sec. 2.2 Teoría de gráficas 129 Al estudiar estructuras organizativas, con frecuencia encontramos subconjuntos de personas en los que cualesquiera dos individuos están relacionado entre sí. Éste es un ejemplo de un clan, término que definimos a continuación. DEFINICIÓN En una digráfica, un clan es un subconjunto S de vértices con las siguientes propiedades: (a) S contiene tres o más vértices. (b) Si Pi y Pj están en S, existe una arista dirigida de Pi a Pj y una arista dirigida de Pj a Pi. (c) No existe un subconjunto T de vértices que satisfaga la propiedad (b) y que conten- ga a S [es decir, S es un subconjunto maximal que satisface (b)]. EJEMPLO 8 Considere la digráfica de la figura 2.9. El conjunto {P1, P2, P3} satisface las condicio- nes (a) y (b) anteriores, pero no es un clan, pues no satisface la condición (c). Es decir, {P1, P2, P3} está contenido en {P1, P2, P3, P4}, el cual satisface las condiciones (a), (b) y (c). En consecuencia, el único clan en esta digráfica es {P1, P2, P3, P4}. ■ P1 P3 P5 P2 P3 P1 P4 P6 P4 P5 P2 Figura 2.9 ᭡ Figura 2.10 ᭡ EJEMPLO 9 Considere la digráfica de la figura 2.10. En este caso tenemos dos clanes: {P1, P2, P3, P4} y {P4, P5, P6}. Además, P4 pertenece a ambos clanes. ■ Es difícil determinar los clanes en el caso de digráficas de gran tamaño. El siguien- te método es útil para detectar clanes y puede implementarse con facilidad en una compu- tadora. Si A(G) = [aij] es la matriz de adyacencia de una digráfica, formamos una nueva matriz S = [sij]: sij = sji = 1 si aij = aji = 1; en caso contrario, hacemos sij = sji = 0. Así, sij = 1 si Pi y Pj tienen acceso uno al otro; en caso contrario, sij = 0. Observe que S es una matriz simétrica (S = ST).

130 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) EJEMPLO 10 Considere una digráfica con matriz de adyacencia P1 ⎡ P1 P2 P3 P4 P5 P6 ⎤ 0 0 1 1 1 0 A(G) = P2 ⎢⎢⎢⎢⎣⎢ 1 0 1 1 1 1 ⎥⎥⎥⎦⎥⎥. P3 0 1 0 1 1 1 P4 1 0 1 0 0 1 P5 1 1 0 1 0 1 P6 0 1 1 1 1 0 Entonces, ⎡ P1 P2 P3 P4 P5 P6 ⎤ P1 ⎢⎣⎢⎢⎢⎢⎢⎢⎢ 0 0 0 1 1 0 ⎥⎥⎦⎥⎥⎥⎥⎥⎥. P2 0 0 1 0 1 S = P3 0 1 0 1 0 1 P4 1 0 1 0 0 1 P5 1 1 0 0 0 1 1 P6 0 1 1 1 1 0 ■ De acuerdo con ello, puede demostrarse el siguiente teorema. TEOREMA 2.2 Sean A(G) la matriz de adyacencia de una digráfica y S = [sij] la matriz simétrica de- = [ si(j3) ], finida previamente, con S3 sólo si la ednotnraddea[dsii(aj3)g]o,neasl,elsi(ej3l)eemsepnotosiit,ivj-a.de S3. Entonces, Pi pertenece a un clan si y ■ Consideremos brevemente por qué nos interesan las entradas diagonales de S3 en el teorema 2.2. En primer lugar, observe que la entrada diagonal si(j3) de S3 proporciona el número de formas en que Pi puede tener acceso a sí mismo en tres etapas. Si si(i3) > 0 , hay por lo menos una forma en que Pi tiene acceso a sí mismo. Como una digráfica no tiene bucles, este acceso debe pasar por dos individuos: Pi → Pj → Pk → Pi. Así, sij 0. Pero sij 0 implica que sij 0, de modo que Pj → Pi. De manera similar, cua- lesquiera dos de los individuos en {Pi, Pj, Pk} tienen acceso uno al otro. Esto significa que Pi, Pj y Pk pertenecen al mismo clan. La dirección opuesta (si Pi está en un clan, entonces si(i3) > 0 ) se deja como ejercicio. El procedimiento para determinar un clan en una digráfica es el siguiente. Paso 1. Si A = [aij] es la matriz de adyacencia de la digráfica dada, calculamos la matriz simétrica S = [sij], donde sij = sji = 1 si aij = aji = 1; y sij = 0 en caso contrario. Paso 2. Calculamos S3 = [ si(j3) ], Paso 3. Pi pertenece a un clan si y sólo si si(j3) es positivo.

Sec. 2.2 Teoría de gráficas 131 EJEMPLO 11 Considere la digráfica de la figura 2.11, cuya matriz de adyacencia es P1 ⎡ P1 P2 P3 P4 P5 ⎤ 0 1 1 0 1 A(G) = P2 ⎢⎢⎢⎣ 1 0 0 0 1 ⎥⎦⎥⎥. P3 1 0 0 1 0 P4 0 1 1 0 0 P1 P2 P5 1 0 0 0 0 P5 P4 Entonces (verifique) Figura 2.11 ᭡ P1 ⎡ P1 P2 P3 P4 P5 ⎤ 0 1 1 0 1 P3 S= P2 ⎢⎢⎣⎢ 1 0 0 0 0 ⎥⎥⎦⎥ P3 1 0 0 1 0 P4 0 0 1 0 0 P5 1 0 0 0 0 y P1 P2 P3 P4 P5 0 3 4 0 3 P1 ⎡ ⎤ S3 = P2 ⎢⎢⎢⎣ 3 0 0 1 0 ⎥⎥⎥⎦. P3 4 0 0 2 0 P4 0 1 2 0 1 P5 3 0 0 1 0 Como cada entrada diagonal de S3 es igual a cero, concluimos que no hay clanes. ■ EJEMPLO 12 Considere la digráfica de la figura 2.12, cuya matriz de adyacencia es P1 ⎡ P1 P2 P3 P4 P5 ⎤ 0 0 1 1 1 P1 P2 A(G) = P2 ⎢⎢⎣⎢ 0 0 1 0 1 ⎥⎦⎥⎥. P3 P3 1 0 0 0 1 P5 P4 0 0 1 0 1 P4 P5 1 1 1 0 0 Figura 2.12 ᭡ Entonces (verifique) P1 ⎡ P1 P2 P3 P4 P5 ⎤ y 0 0 1 0 1 S= P2 ⎢⎢⎢⎣ 0 0 0 0 1 ⎦⎥⎥⎥ P3 1 0 0 0 1 P4 0 0 0 0 0 P5 1 1 1 0 0 P1 ⎡ P1 P2 P3 P4 P5 ⎤ 2 1 3 0 4 S3 = P2 ⎢⎢⎢⎣ 1 0 1 0 3 ⎦⎥⎥⎥. P3 3 1 2 0 4 P4 0 0 0 0 0 P5 4 3 4 0 2 Como s11, s33 y s55 son positivos, concluimos que P1, P3 y P5 pertenecen a algún clan; de hecho, forman el único clan en esta digráfica. ■

132 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) Consideremos ahora el concepto de digráfica (o gráfica dirigida) fuertemente conexa. DEFINICIÓN En una digráfica, una trayectoria (o camino) que une a dos vértices Pi y Pk, es una su- cesión de vértices distintos Pi, Pa, Pb, Pc, . . . , Pr, Pk y aristas dirigidas PiPa, PaPb, . . . , PrPk. EJEMPLO 13 Considere la digráfica de la figura 2.13. La sucesión P2 → P3 → P4 → P5 es una trayectoria. La sucesión P2 → P3 → P4 → P2 → P5 no es una trayectoria, pues se repite el vértice P2. ■ Figura 2.13 ᭤ P1 P3 P2 P4 DEFINICIÓN P5 P6 La digráfica G es fuertemente conexa si para cualesquiera dos vértices distintos Pi y Pj existe una trayectoria de Pi a Pj y una trayectoria de Pj a Pi. En caso contrario, G no es fuertemente conexa. Un ejemplo de una digráfica fuertemente conexa son las calles de una ciudad. En el caso de muchas digráficas, determinar si son o no fuertemente conexas resul- ta tedioso. En primer lugar, observe que si nuestra digráfica tiene n vértices, el número de aristas en una trayectoria de Pi a Pj no puede exceder n – 1, pues todos los vérti- ces de la misma son distintos y es imposible recorrer más vértices que los n de la digrá- fica. Si [ A(G)]r = [bi(rj )], entonces bi(rj ) es el número de formas de ir de Pi a Pj en r etapas. Una forma de ir de Pi a Pj en r etapas no es necesariamente una trayectoria, pues podría tener vértices repetidos. Si éstos y todas las aristas entre ellos se eliminan, real- mente obtenemos una trayectoria entre Pi y Pj con no más de r aristas. Por ejemplo, si tenemos P1 → P2 → P4 → P3 → P2 → P5, podemos eliminar el segundo vértice P2 y todas las aristas entre los vértices P2, obteniendo la trayectoria P1 → P2 → P5. Por lo tanto, si el elemento i, j- de [A(G)] + [A(G)]2 + · · · + [A(G)]n−1 es igual a cero, entonces no hay una trayectoria de Pi a Pj. De acuerdo con lo anterior, el siguiente teorema, la mitad de cuya demostración acabamos de bosquejar, proporcio- na un criterio para las digráficas fuertemente conexas. TEOREMA 2.3 Una digráfica con n vértices es fuertemente conexa si y sólo si su matriz de adyacen- cia A(G) tiene la propiedad de que la matriz [A(G)] + [A(G)]2 + · · · + [A(G)]n−1 = E ■ no tiene entradas iguales a cero.

Sec. 2.2 Teoría de gráficas 133 El procedimiento para determinar si una digráfica G con n vértices es fuertemente conexa es el siguiente. Paso 1. Si A(G) es la matriz de adyacencia de la digráfica, calculamos [A(G)] + [A(G)]2 + · · · + [A(G)]n−1 = E. Paso 2. G es fuertemente conexa si y sólo si E no tiene entradas iguales a cero. EJEMPLO 14 Considere la digráfica de la figura 2.14. La matriz de adyacencia es P1 ⎡ P1 P2 P3 P4 P5 ⎤ 0 1 0 1 0 P2 A(G) = P2 ⎢⎣⎢⎢ 0 0 1 1 0 ⎦⎥⎥⎥. P1 P3 0 0 0 1 1 P4 1 0 1 0 0 P4 P3 P5 0 1 0 1 0 Entonces (verifique) P1 ⎡ P1 P2 P3 P4 P5 ⎤ 5 5 7 10 3 P5 A(G)+[ A(G)]2+[ A(G)]3+[ A(G)]4 = E = P2 ⎣⎢⎢⎢ 5 4 8 10 3 ⎥⎦⎥⎥. P3 5 4 7 10 4 P4 5 4 7 10 4 P5 5 5 7 10 3 Figura 2.14 ᭡ Como todas las entradas de E son positivas, la digráfica dada es fuertemente conexa. ■ Este enfoque sirve, por ejemplo, para rastrear la propagación de un contaminante en un grupo de individuos; si hay una trayectoria de Pi a Pj, el contaminante puede pro- pagarse de Pi a Pj. Lecturas adicionales BERGE, C., The Theory of Graphs and Its Applications, Nueva York: Dover Publica- tions, 2001. BUSACKER, R.G. y T.L. SAATY, Finite Graphs and Networks: An Introduction with Ap- plications, Nueva York, McGraw-Hill, 1965. CHARTRAND, GARY y LINDA LESNIAK, Graphs and Digraphs, 4a. ed., Boca Ratón: CRC Press, 2004. CHARTRAND, GARY y P. ZHANG, Introduction to Graph Theory, Nueva York: McGraw- Hill, 2004. JOHNSTON, J.B., G. PRICE y F.S. VAN VLECK, Linear Equations and Matrices, Reading, Massachusetts: Addison-Wesley Publishing Company, Inc., 1966. KOLMAN, B., R.C. BUSBY y S. ROSS, Discrete Mathematical Structures, 5a. ed., Upper Saddle River, Nueva Jersey: Prentice Hall, Inc., 2004. ORE, O., Graphs and Their Uses, 2a. ed. revisada, Washington, D.C.: Mathematical As- sociation of America, 1996. TRUDEAU, R.J., Introduction to Graph Theory, Nueva York: Dover, 2002. TUCKER, ALAN, Applied Combinatorics, 4a. ed., Nueva York, Wiley, 2002.

134 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) Términos clave Matriz de adyacencia Clan Gráficas (o digráficas) de dominancia Fuertemente conexa Gráfica dirigida (digráfica) Acceso en dos etapas Vértices (o nodos) Arcos (aristas o lados) dirigidos 2.2 Ejercicios 1. En cada caso, trace una digráfica determinada por la Carter influye en Smith y Gordon. Gordon influye en Jones. matriz dada. Smith se ve influenciado por Peters. Russell se ve influenciado por Carter, Smith y Gordon. ⎡0 1 0 0 0⎤ Peters se ve influenciado por Russell. Jones influye en Carter y Russell. (a) ⎣⎢⎢⎢110 0 1 1 101⎥⎥⎥⎦ Smith influye en Jones. 0 0 1 Carter se ve influenciado por Peters. 1 0 0 Peters influye en Jones y Gordon. 10110 (a) ¿Quién influye sobre más personas? ⎡0 1 1 1⎤ (b) ¿Quién se ve influenciado por más personas? (b) ⎣⎢11 0 0 01⎦⎥ 6. Considere una red de comunicación entre cinco indivi- 1 0 duos, descrita con matriz de adyacencia 0100 2. Escriba las matrices de adyacencia de cada una de las digráficas dadas. P2 P2 ⎡ P1 P2 P3 P4 P5 ⎤ P3 0 1 1 1 1 P1 P4 P1 P3 P1 P5 P2 ⎢⎢⎣⎢ 0 0 0 1 1 ⎥⎥⎦⎥. P5 P4 (b) P6 P3 0 1 0 1 0 (a) P4 0 0 0 0 1 P5 1 0 1 0 0 3. Considere un grupo de cinco personas, P1, P2, P3, P4 y (a) ¿De cuántas formas tiene acceso P2 a P1 por medio de P5, que están encargadas de operar una estación climato- un individuo? lógica en una isla remota. Se han observado las siguientes (b) ¿Cuál es el número mínimo de personas por medio de interacciones sociales entre ellas: las cuales P2 tiene acceso a sí misma? P1 se lleva bien con P2, P3 y P4. 7. Considere la siguiente relación de influencia entre cinco P2 se lleva bien con P1 y P5. individuos. P3 se lleva bien con P1, P2 y P4. P4 se lleva bien con P2, P3 y P5. P1 influye en P2, P4 y P5. P5 se lleva bien con P4. P2 influye en P3 y P4. P3 influye en P1 y P4. Trace una digráfica G que describa esta situación. Escriba P4 influye en P5. P5 influye en P2 y P3. la matriz de adyacencia que representa a G. (a) ¿Puede P4 influir en P1 en dos etapas como máximo? 4. ¿Cuáles de las siguientes pueden ser matrices de adyacen- cia de una digráfica de dominancia? (b) ¿De cuántas formas influye P1 en P4 en exactamente tres etapas? ⎡0 1 1 0⎤ (c) ¿De cuántas formas influye P1 en P4 en una, dos o (a) ⎣⎢00 0 1 10⎥⎦ tres etapas? 0 0 0010 En los ejercicios 8 a 10, encuentre un clan —si lo hay— para la digráfica con la matriz de adyacencia dada. ⎡0 0 1 0 0⎤ (b) ⎢⎢⎢⎣110 0 1 0 111⎥⎥⎦⎥ ⎡0 0 0 0 0⎤ 0 0 0 1 1 0 8. ⎢⎣⎢⎢101 0 1 1 001⎦⎥⎥⎥ 1 0 1 10000 1 1 0 5. Los siguientes datos han sido recopilados en un estudio 00110 sociológico de seis personas:

Sec. 2.3 Creación de gráficos por computadora 135 ⎡0 1 1 0 1 1⎤ ⎡0 1 0 0 0⎤ 9. ⎢⎢⎢⎢⎢⎣1101 0 0 0 0 1001⎦⎥⎥⎥⎥⎥ (b) ⎢⎣⎢⎢100 0 1 0 010⎥⎦⎥⎥ 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 00110 101110 ⎡0 1 1 0 1⎤ 13. Determine si la digráfica con la matriz de adyacencia dada es fuertemente conexa. 10. ⎢⎢⎣⎢101 0 1 1 011⎥⎦⎥⎥ 0 0 1 ⎡0 0 1 1 1⎤ 0 0 0 (a) ⎢⎢⎢⎣010 0 1 1 100⎦⎥⎥⎥ 01010 1 0 0 1 0 0 11. Considere una red de comunicación entre cinco individuos, descrita con la matriz de adyacencia 11000 ⎡0 1 0 0 0⎤ ⎡0 0 0 0 1⎤ ⎢⎢⎢⎣010 0 1 0 100⎦⎥⎥⎥ . (b) ⎢⎢⎢⎣010 0 1 1 010⎥⎥⎥⎦ 0 0 1 1 0 0 1 0 0 0 0 0 00110 00010 (a) ¿P3 puede enviar un mensaje a P5 en dos etapas cuan- 14. Un grupo de cinco acróbatas realiza una pirámide humana, do mucho? en la cual debe haber una trayectoria de soporte entre cua- (b) ¿Cuál es el número mínimo de etapas que garantizará que cada persona puede enviar un mensaje a cualquie- lesquiera dos personas distintas, pues de lo contrario la ra otra (que no sea ella misma)? pirámide caerá. En la siguiente matriz de adyacencia, aij = 1 significa que Pi soporta a Pj: (c) ¿Cuál es el número mínimo de etapas que garantizaría que cada persona puede enviar un mensaje a cualquie- ⎡0 0 1 1 0⎤ ra otra (inclusive ella misma)? ⎢⎢⎢⎣111 0 0 0 110⎦⎥⎥⎥ . 12. Determine si la digráfica con la matriz de adyacencia dada 0 0 1 0 0 0 es fuertemente conexa. ⎡0 1 1 1⎤ 01100 (a) ⎣⎢10 0 1 11⎦⎥ ¿Quién puede retirarse de la pirámide sin provocar que és- 0 0 ta se caiga? 0010 Ejercicios teóricos T.2. Demuestre el teorema 2.1. T.3. Demuestre el teorema 2.2. T.1. Demuestre que una digráfica que tiene aristas dirigidas PiPj y PjPi no puede ser una gráfica de dominancia. Ejercicios con MATLAB ⎡0 1 1 0 1⎤ En MATLAB, Los operadores + y ^ permiten calcular sumas y ⎢⎣⎢⎢010 0 0 1 101⎦⎥⎥⎥ . potencias de una matriz. Por lo tanto, los cálculos de los teore- 1 0 0 mas 2.2 y 2.3 pueden realizarse fácilmente en dicho software. 1 1 0 ML.1. Resuelva el ejercicio 8 utilizando MATLAB. 10010 ML.2. Determine un clan —si lo hay— para la digráfica con ML.3. Resuelva el ejercicio 13 utilizando MATLAB. la siguiente matriz de adyacencia: 2.3 CREACIÓN DE GRÁFICOS POR COMPUTADORA Requisito. Lectura de la sección 1.5, Transformaciones matriciales. Todos estamos familiarizados con los sorprendentes resultados que se logran con ayu- da de computadoras en la creación de gráficos destinados a los juegos de vídeo y a los

136 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) EJEMPLO 1 efectos especiales en la industria del cine. La creación de gráficos por computadora también desempeña un papel importante en el mundo de la manufactura. Por ejemplo, el diseño asistido por computadora (CAD, por sus siglas en inglés) se emplea para di- señar modelos de los productos y luego someterlos (también en computadora) a una se- rie de pruebas para, finalmente, implementar las modificaciones necesarias a fin de lograr un mejor diseño. Uno de los éxitos más notables de este método se ha consegui- do en la industria automotriz, en donde los modelos automovilísticos pueden verse des- de diversos ángulos hasta encontrar un estilo más atractivo y popular, así como verificar la resistencia de sus componentes, su adaptabilidad al camino, la comodidad de sus asientos, la seguridad que ofrecen en caso de choque, etcétera. En esta sección veremos ejemplos de transformaciones matriciales f : R2 → R2 que son útiles en el desarrollo de gráficos bidimensionales. Sea f : R2 → R2 la transformación matricial que realiza una reflexión respecto del eje x. (Vea el ejemplo 5 de la sección 1.5.) Entonces, f se define mediante f(v) = Av, donde A= 1 0 . 0 −1 Por lo tanto, tenemos f (v) = Av = 1 0 x = x . 0 −1 y −y Para ilustrar una reflexión respecto del eje x en la creación de gráficos por compu- tadora, sea T el triángulo de la figura 2.15(a), con vértices (−1, 4), (3, 1) y (2, 6). Para reflejar T respecto del eje x, hacemos v1 = −1 , v2 = 3 , v3 = 2 4 1 6 y calculamos las imágenes f(v1), f(v2) y f(v3) formando los productos Av1 = 1 0 −1 = −1 , 0 −1 4 −4 Av2 = 1 0 3 = 3 , 0 −1 1 −1 Av3 = 1 0 2 = 2 . 0 −1 6 −6 Estos tres productos pueden escribirse en términos de matrices por bloques como A v1 v2 v3 = −1 3 2 . −4 −1 −6 En consecuencia, la imagen de T tiene vértices (−1, −4), (3, −1) y (2, −6), como se muestra en la figura 2.15(b). ■

Sec. 2.3 Creación de gráficos por computadora 137 Figura 2.15 ᭤ y y 66 44 22 –6 –4 –2–2 x – 6 – 4 –2–2 x 246 246 –4 –4 –6 –6 (a) (b) EJEMPLO 2 La transformación matricial f : R2 → R2 que realiza una reflexión respecto de la recta y = −x se define mediante f(v) = Bv, y donde 6 B= 0 −1 . 4 −1 0 2 x Para ilustrar la reflexión respecto de la recta y = −x, utilizamos el triángulo T definido –22 4 6 en el ejemplo 1, y calculamos los productos –4 –6 –4 –2 –6 B v1 v2 v3 = 0 −1 −1 3 2 = −4 −1 −6 . −1 0 4 1 6 1 −3 −2 Por lo tanto, la imagen de T tiene vértices Figura 2.16 ᭡ (−4, 1), (−1, −3) y (−6, −2), tal como aparece en la figura 2.16. ■ Para realizar una reflexión respecto del eje x para el triángulo T del ejemplo 1, se- guida por una reflexión respecto de la recta y = −x, calculamos B(Av1), B(Av2) y B(Av3). Es fácil demostrar que al invertir el orden de estas transformaciones matriciales se ob- tiene una imagen diferente (verifique). Esto muestra que el orden en que se realizan las transformaciones es importante, lo cual es comprensible, ya que la multiplicación de matrices, a diferencia de la multiplicación de números reales, no satisface la propiedad conmutativa. EJEMPLO 3 Las rotaciones en un plano se definieron en el ejemplo 9 de la sección 1.5. Una figura plana se gira en sentido contrario al giro de las manecillas del reloj, en un ángulo q, por medio de la transformación matricial f : R2 → R2, definida por f(v) = Av, donde A= cos φ − sen φ . sen φ cos φ Ahora suponga que queremos rotar la parábola y = x2 en sentido contrario a las ma- necillas del reloj, en un ángulo de 50°. Primero elegimos algunos puntos de la parábo- la, digamos, (−2, 4), (−1, 1), (0, 0), 1 , 1 y (3, 9) 2 4

138 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) [vea la figura 2.17(a)]. Luego calculamos las imágenes de estos puntos. De esta mane- ra, si ⎡⎤ −2 −1 0 1 3 4 1 0 9 v1 = , v2 = , v3 = , v4 = ⎣2⎦ , v5 = , 1 4 calculamos los productos (con cuatro cifras decimales) (verifique) A v1 v2 v3 v4 v5 = −4.3498 −1.4088 0 0.1299 −4.9660 . 1.0391 −0.1233 0 0.5437 8.0832 A continuación trazamos los puntos imagen (−4.3498, 1.0391), (−1.4088, −0.1233), (0,0), (0.1299, 0.5437) y (−4.9660, 8.0832) y los conectamos para obtener una aproximación de la imagen de la parábola, como se ilustra en la figura 2.17(b). ■ Figura 2.17 ᭤ y y 88 66 44 22 O2 x O2 x – 4 –2 4 – 4 –2 4 (a) (b) Las rotaciones son particularmente útiles en la obtención de efectos sofisticados pa- ra juegos de vídeo y para demostraciones animadas por computadora. Por ejemplo, para lograr la ilusión de una rueda girando, podemos rotar los rayos en un ángulo e1, luego en un ángulo e2, y así sucesivamente. Sean u = a1 el 2-vector que representa un a2 rayo de la rueda, y f : R2 → R2 la transformación matricial definida por f(v) = Av, donde A= cos θ1 − sen θ1 ; sen θ1 cos θ1 y sea g: R2 → R2 la transformación matricial definida por g(v) = Bv, donde B= cos θ2 − sen θ2 . sen θ2 cos θ2 La sucesión de rotaciones del rayo u se representa mediante g( f (u)) = g(Au) = B(Au).

Sec. 2.3 Creación de gráficos por computadora 139 El producto Au se realiza primero, y genera una rotación de u en un ángulo e 1; luego el producto B(Au) genera la segunda rotación. Tenemos B(Au) = B(a1col1(A) + a2col2(A)) = a1Bcol1(A) + a2Bcol2(A) y la última expresión es una combinación lineal de los vectores columna Bcol1(A) y Bcol2(A), que podemos escribir como el producto Bcol1( A) Bcol2( A) a1 . a2 Con base en la definición de multiplicación de matrices, [Bcol1(A) Bcol2(A)] = BA, así que tenemos B(Au) = (BA)u. Esto indica que en lugar de aplicar en sucesión las transformaciones, es decir, f segui- da por g, podemos obtener el mismo resultado formando el producto matricial BA y usándolo para definir una transformación matricial sobre los rayos de la rueda. EJEMPLO 4 Un inclinación (o corte) en la dirección x es la transformación matricial definida por f (v) = 1 k v, 0 1 donde k es un escalar. Una inclinación en la dirección x lleva el punto (x, y) hasta el pun- to (x + ky, y). Es decir, el punto (x, y) se mueve en forma paralela al eje x, en una can- tidad ky. Consideremos ahora el rectángulo R, que se muestra en la figura 2.18(a), con vér- tices (0, 0), (0, 2), (4, 0) y (4, 2). Si aplicamos la inclinación en la dirección x con k = 2, la imagen de R es el paralelo- gramo con vértices (0, 0), (4, 2), (4, 0) y (8, 2), tal como se ilustra en la figura 2.18(b). Si aplicamos la inclinación en la dirección x con k = −3, la imagen de R es el paralelogramo con vértices (0, 0), (−6, 2), (4, 0) y (−2, 2), como se muestra en la figura 2.18(c). ■ En el ejercicio 3 consideraremos inclinaciones en la dirección y. Figura 2.18 ᭤ y y y 4 4 Inclinación k = 2 Inclinación k = –3 4 2 2 2 O 246 x O 2468 x x (a) (b) – 6 – 4 –2 O 2 46 (c)

140 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) En los ejercicios que se plantean al final de la sección, se consideran otras trans- formaciones matriciales utilizadas en la creación de gráficas bidimensionales por compu- tadora. Para un análisis detallado de este tema, consulte la bibliografía que se indica al final de la sección. En los ejemplos 1 y 2 aplicamos la transformación matricial a un triángulo, figura que puede ser especificada si se tienen sus tres vértices. En el ejemplo 3, la figura que fue transformada fue una parábola, que no puede especificarse con un número finito de puntos. En este caso, se optó por un cierto número de puntos de la parábola para apro- ximarse a su forma y se calcularon las imágenes de estos puntos aproximativos que, juntos, dieron una forma aproximada de la imagen de la figura. EJEMPLO 5 Sea f : R2 → R 2 la transformación matricial definida por f (v) = Av, donde A= h 0 0 k con h y k diferentes de cero. Ahora suponga que deseamos aplicar esta transformación matricial a una circunferencia de radio 1 y centro en el origen (la circunferencia unita- ria). Desafortunadamente una circunferencia no puede especificarse mediante un núme- ro finito de puntos. Sin embargo, cada uno de los puntos de la circunferencia unitaria se describe mediante un par ordenado (cos θ, sen θ ), donde el ángulo θ toma todos los valores de 0 a 2/ radianes. En consecuencia, ahora podemos representar un punto arbitrario en la circunferencia unitaria mediante el vector u = cos θ . De esta manera, sen θ las imágenes de la circunferencia unitaria que se obtienen mediante la aplicación de la transformación matricial f están dadas por f (u) = Au = h 0 cos θ = h cos θ = x . 0 k sen θ k sen θ y Recordemos que una circunferencia de radio 1 y centro en el origen se describe median- te la ecuación x2 + y2 = 1. Según la identidad pitagórica, sen2 θ + cos2 θ = 1. Por lo tanto, los puntos (cos θ, sen θ) están en la circunferencia unitaria. Ahora queremos obtener una ecuación que des- criba la imagen de la circunferencia unitaria. Tenemos xЈ = h cos θ y yЈ = k sen θ de manera que x = cos θ, y = sen θ. h k De acuerdo con lo anterior, x 2 y 2 h k + = 1, que es la ecuación de una elipse. Esto muestra que la imagen de la circunferencia uni- taria obtenida mediante la transformación matricial f, es una elipse con centro en el ori- gen. Vea la figura 2.19. ■ Lecturas adicionales FOLEY, J.D., A. VAN DAM, S.K. FEINER, J.F. HUGHES y R.L. PHILLIPS, Introduction to Computer Graphics, 2a. ed., Reading, Massachusetts: Addison-Wesley, 1996.

Sec. 2.3 Creación de gráficos por computadora 141 Figura 2.19 ᭤ Circunferencia unitaria Elipse MORTENSON, M.E. Mathematics for Computer Graphics Applications, 2a. ed., Nueva York: Industrial Press, Inc., 1999. ROGERS, D.F. y J.A. ADAMS, Mathematical Elements for Computer Graphics, 2a. ed., Nueva York, McGraw-Hill, 1989. Términos clave Reflexión Dilatación Rotación Contracción Creación de gráficos por computadora Inclinación (corte) Diseño asistido por computadora (CAD) Imagen 2.3 Ejercicios 5. La transformación matricial f : R2 → R 2 definida por f (v) = Av, donde 1. Sea f : R2 → R2 la transformación matricial definida por f (v) = Av, donde A= −1 0 , A= k 0 , 0 1 0 1 esto es, f es una reflexión respecto del eje y. Determine y y k es un número real, es una dilatación en dirección x si bosqueje la imagen del rectángulo R con vértices (1, 1), k > 1, y es una contracción en dirección x si 0 < k < 1. (2, 1), (1, 3) y (2, 3). Si R es el cuadrado unitario y si f es la dilatación en direc- ción x con k = 2, determine y bosqueje la imagen de R. 2. Sea R el rectángulo con vértices (1, 1), (1, 4), (3, 1) y (3, 4). Sea f la inclinación en dirección x con k = 3. 6. La transformación matricial f : R2 → R 2 definida por Determine y bosqueje la imagen de R. f (v) = Av, donde 3. Una inclinación (o corte) en dirección y es la transforma- A= 1 0 , ción matricial f : R2 → R 2, definida por f (v) = Av, donde 0 k 1 0 y k es un número real, es una dilatación en dirección y si k k 1 A= , > 1, y es una contracción en dirección y si 0 < k < 1. Si R es el cuadrado unitario y f es la contracción en direc- y k es un escalar. Sea R el rectángulo que se definió en ción y con k = 1 , determine y bosqueje la imagen de R. el ejercicio 2, y sea f la inclinación en dirección y con 2 k = −2. Determine y bosqueje la imagen de R. 7. Sea T el triángulo con vértices (5, 0), (0, 3) y (2, –1). Deter- 4. La transformación matricial f : R2 → R2 definida por f (v) = Av, donde mine las coordenadas de los vértices de la imagen de T bajo la transformación matricial f, definida por A= k 0 , f (v) = −2 1 v. 0 k 3 4 y k es un número real, se denomina dilatación si k > 1, y 8. Sea T el triángulo con vértices (1, 1), (−3, −3) y (2, −1). contracción si 0 < k < 1. En consecuencia, la dilatación es- Determine las coordenadas de los vértices de la imagen de tira un vector, mientras que la contracción lo comprime. Si R T bajo la transformación matricial definida por es el rectángulo que se definió en el ejercicio 2, determine y bosqueje la imagen de R para 4 −3 −4 2 (a) k = 4 (b) k = 1 f (v) = v. 4

142 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) 9. Sea f la rotación en sentido contrario a las manecillas del (b) y reloj y en un ángulo de 60°. Si T es el triángulo definido en el ejercicio 8, determine y dibuje la imagen de T bajo f. –1 O x 10. Sea f1 la reflexión respecto del eje y, y sea f2 una rotación –1 en sentido contrario a las manecillas del reloj, en un ángulo 15. Sea S el triángulo que se muestra en la figura. de //2 radianes. Demuestre que el resultado de realizar pri- mero f2 y luego f1 no es el mismo que realizar primero f1 y y luego f2. 2 11. Sean A la matriz singular 1 2 y T el triángulo definido 24 en el ejercicio 8. Describa la imagen de T bajo la transfor- mación matricial f : R2 → R2 definida por f (v) = Av. 12. Sea f la transformación matricial definida en el ejemplo 5. Determine y dibuje la imagen del rectángulo con vértices (0, 0), (1, 0), (1, 1) y (0, 1) para h = 2 y k = 3. 13. Sea f : R2 → R2 la transformación matricial definida por f (v) = Av, donde A= 1 −1 . –2 O x 2 3 –2 2 Determine y dibuje la imagen del rectángulo definido en el Determine dos maneras distintas de emplear las transforma- ejercicio 12. ciones anteriores sobre S para obtener la imagen dada. Pue- de aplicar en sucesión más de una transformación matricial. En los ejercicios 14 y 15, sean f1, f 2 , f 3 y f 4 las siguientes trans- (a) formaciones matriciales: y f1 : rotación en sentido contrario a las manecillas del reloj, en un ángulo φ 2 f2 : reflexión respecto del eje x f3 : rotación respecto del eje y f4 : rotación respecto de la recta y = x 14. Sea S el cuadrado unitario. y 1 –2 O x 2 O x –2 1 Determine dos maneras distintas de utilizar las transforma- ciones matriciales anteriores sobre S para obtener la imagen dada. Puede aplicar en sucesión más de una transformación matricial. y (a) y (b) 2 Ox O –2 x 2 –2

Sec. 2.3 Creación de gráficos por computadora 143 Ejercicios con MATLAB En esta sección se analizaron las transformaciones matriciales. continuación aparecerá el cuadrado unitario en el con- Son funciones, cuya entrada y salida son vectores relacionados junto de ejes a la izquierda. por medio de una multiplicación matricial: f (c) = Ac. La entra- (a) Ahora haga clic en el botón MATRIX, e introduzca da c puede ser un solo vector o una colección de vectores que representn una figura u objeto. (Observe que podemos visuali- la matriz A= 2 0 escribiendo [2 0;0 4]; zar los vectores como puntos, y viceversa.) Una transformación 0 4 matricial de Rm a Rn suele denominarse transformación o mapeo. presione Enter. Haga clic en el botón MAP IT para ver la imagen del cuadrado unitario determinado En los ejemplos geométricos de esta sección se tomó A por la matriz A. ¿Cuál es el área de la imagen? como una matriz de 2 × 2, para poder mostrar fácilmente la (b) Haga clic en el botón Composite y luego en el botón salida o resultado, es decir, la imagen. En los ejercicios siguien- MATRIX que se despliega. Esta vez ingrese la matriz tes continuaremos esta práctica, y utilizaremos MATLAB para construir gráficas de las imágenes. Las rutinas de MATLAB 1 0 , utilizadas en estos ejercicios le dan la oportunidad de adquirir 2 experiencia mediante la visualización de transformaciones 1 matriciales. 0 4 En los ejercicios ML.1 a ML.4, utilice la rutina de MATLAB matrixtrans para generar ilustraciones y capacidades experi- y haga clic en MAP IT. ¿Cuál es el área de la ima- mentales adicionales. Escriba help matrixtrans en MATLAB, y gen compuesta? lea la breve descripción. Para iniciar esta rutina, escriba ma- trixtrans. En la parte inferior izquierda está la Comment Win- (c) Si A= 2 0 yB= 1 0 , vimos que dow (Ventana de comentarios), que le proporcionará 0 4 2 instrucciones sobre los pasos para usar esta rutina. 1 0 4 f (cuadrado unitario) = A(cuadrado unitario) = primera imagen y ML.1. Seleccione el ‘Object’ Circle (Círculo) haciendo clic en g(primera imagen) = B(primera imagen) la palabra. Vea la ventana de comentarios; luego haga = imagen compuesta. clic en el botón View. En la pantalla de visualización En consecuencia, tenemos aparecerá la circunferencia unitaria en el conjunto de g( f (cuadrado unitario)) = B(A(cuadrado unitario)) ejes a la izquierda. = imagen compuesta. (a) Haga clic en el botón MATRIX, y luego ingrese la Calcule la matriz AB y explique cómo se relaciona el resultado de esta composición con el cuadrado unitario. matriz A= 0.5 0 ML.3. (Inicie matrixtrans; o, si ya está usando la rutina, haga 0 1 clic en Restart.) Seleccione el‘Object’ House haciendo clic en la palabra. Vea la ventana de escribiendo [0.5 0;0 1]; al terminar presione Enter comentarios. Haga clic en el botón View. A continuación (Intro). Haga clic en el botón MAP IT para ver la aparecerá la casa en el conjunto de ejes a la izquierda. imagen de la circunferencia unitaria determinada (a) Haga clic en el botón Grid On. Calcule el área de por la matriz A. la casa. Utilice una transformación matricial que (b) Haga clic en el botón Composite y luego en el bo- sea una inclinación en dirección x, con k = 1 (vea tón MATRIX que se desplegará. Ahora vuelva a in- el ejemplo 4), y muestre la imagen. ¿Cuál es el troducir la matriz área de la imagen? ¿Cómo se relacionan las áreas? (b) Haga clic en el botón Restart. Seleccione una vez 0.5 0 más la casa. Utilice una transformación matricial 01 que produzca una inclinación en dirección x con k = 0.5 (vea el ejemplo 4), y muestre la imagen. (o utilice la flecha hacia arriba para tener acceso a ¿Cuál es el área de la imagen? la pila de comandos para encontrar esta matriz); (c) Haga clic en el botón Restart. Seleccione otra vez la luego haga clic en MAP IT. casa. Utilice una transformación matricial que pro- (c) Escriba una breve descripción de las acciones reali- duzca una inclinación en dirección x, con k = 2 (vea zadas por las transformaciones matriciales en los el ejemplo 4), y muestre la imagen. ¿Cuál es el área incisos (a) y (b). de la imagen? (Inspeccione cuidadosamente la (d) Si aplicamos esta misma transformación una terce- figura.) ra vez, ¿en dónde estará la imagen, en relación con la figura actual? ML.4. Utilice matrixtrans para realizar lo siguiente. (a) Seleccione el objeto Arrow (Flecha). Determine ML.2. (Inicie matrixtrans; o, si ya está usando la rutina, haga una matriz A tal que la imagen sea una flecha que clic en Restart.) Seleccione el ‘Object’ Square (Cua- apunta en la dirección opuesta. Muestre la imagen. drado), haciendo clic en la palabra. Vea la ventana de comentarios. Luego haga clic en el botón View. A

144 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) (b) Seleccione el objeto Arrow (Flecha). Determine (b) Invierta el orden de las transformaciones propues- una matriz A tal que la imagen sea una flecha que tas en la parte (a). Conserve un bosquejo de la fi- apunta en la misma dirección, pero de la mitad de gura obtenida con esta composición. Compare largo. Muestre la imagen. este dibujo con el de la parte (a). Si A es la matriz de la rotación de 45° y B es la matriz de la refle- (c) Seleccione el objeto Arrow y utilice la matriz de xión alrededor del eje y, explique cómo sabemos MATLAB que BA AB. cos(pi/4) sen(pi/4) . ML.6. Utilice planelt con el paralelogramo. Elija una com- − sen(pi/4) cos(pi/4) posición de transformaciones, de modo que la figura final sea la que se muestra a continuación. Describa la imagen resultante. ¿Qué ángulo forma con la parte positiva del eje horizontal? Como 2 ayuda para responder esta pregunta, utilice el bo- tón de la cuadrícula (grid) y luego analice la cua- 0 drícula generada en la flecha transformada. (d) Utilizando la parte (c), determine las coordenadas –2 del extremo superior de la flecha. En los ejercicios ML.5 y ML.6, utilice la rutina planelt. Las – 4– 6 – 4 –2 0 2 transformaciones matriciales de R2 a R2 se conocen como trans- formaciones lineales del plano. La rutina planelt de MATLAB ML.7. Las proyecciones ortogonales desempeñan un papel nos permite experimentar con tales transformaciones, mediante fundamental en una gran variedad de situaciones que la selección de la operación geométrica que queremos realizar se plantearán posteriormente. Aunque en esta sección sobre una figura. La rutina utiliza la matriz adecuada para utilizamos álgebra para calcular proyecciones, MATLAB calcular la imagen, muestra la matriz y conserva un registro puede ayudarnos a presentar los aspectos geométricos. gráfico de la imagen original, así como de las imágenes ante- Escriba en MATLAB help project y lea la descripción. rior y actual. La rutina planelt es muy versátil, ya que usted Para iniciar la rutina correspondiente, escriba project, puede darle como entrada una matriz o figura propias. Para y luego seleccione la demostración para ver cómo iniciar esta rutina, simplemente escriba planelt. funciona. Utilice project para determinar proywu; es- to es, la proyección de u sobre w, para cada uno de ML.5. Inicie la rutina planelt. Lea las descripciones que apa- los pares de vectores siguientes. Determine si la longi- recen en pantalla, y sígalas hasta llegar a FIGURE tud de la proyección es mayor que la del vector w, y CHOICES. Seleccione entonces el triángulo, elija si está en la dirección opuesta. ‘See the Triangle’ y luego la opción ‘Use this Figure. Go to select transformations’. (a) u = 5 ,w= 3 4 1 (a) Seleccione la rotación y utilice un ángulo de 45°. Después de que se muestren las figuras, presione (b) u = 1 ,w= 3 Enter. Verá nuevamente el menú de opciones de −4 7 Transformaciones Lineales del plano. Si en este punto elige una transformación, se producirá la ⎡⎤ ⎡ ⎤ composición con la transformación que se acaba 53 de aplicar. Inténtelo, eligiendo reflejar la figura ac- (c) u = ⎣3⎦, w = ⎣ 1⎦ tual alrededor del eje y. Las figuras que se exhiben muestran el triángulo original, el triángulo rotado 1 −4 45°, y después esta imagen reflejada alrededor del eje y. Conserve un bosquejo de la figura compuesta. ⎡⎤ ⎡⎤ 42 (d) u = ⎣6⎦, w = ⎣3⎦ 08 2.4 CIRCUITOS ELÉCTRICOS Requisito. Lectura de la sección 1.6, Soluciones de sistemas de ecuaciones lineales. En esta sección presentaremos las leyes básicas del análisis de los circuitos eléctricos, y luego las emplearemos para analizar circuitos eléctricos formados por baterías, resis- tores (resistencias) y cables. Una batería (o pila) es una fuente de corriente directa (o voltaje) en el circuito; una resistencia es un dispositivo, como un foco, que reduce la corriente en un circui- to y convierte la energía eléctrica en energía térmica, y un cable es un conductor que

Sec. 2.4 Circuitos eléctricos 145 permite el libre flujo de corriente eléctrica. Un circuito eléctrico sencillo es una cone- xión cerrada de resistencias, baterías y cables. Cuando los circuitos se representan por medio de diagramas, las baterías, resistencias y cables se denotan como sigue: Baterías Resistencias Cables b c d La figura 2.20 muestra un circuito eléctrico sencillo, formado por tres baterías y cuatro R E R! resistencias, unidas mediante cables. E R E! Las cantidades físicas que se utilizan al analizar los circuitos eléctricos son la co- rriente, la resistencia y la diferencia de potencial eléctrico en una batería. La diferencia af R\" de potencial eléctrico se mide en voltios (V) y se denota mediante E. La corriente se de- e nota con I y se mide en amperios (A). La resistencia se denota con R y se mide en ohms Figura 2.20 ᭡ (1). Estas unidades se relacionan mediante la ecuación Un voltio = (un amperio) × (un ohm). La diferencia de potencial eléctrico de una batería se considera positiva si se mide de la terminal negativa (−) a la positiva (+), y negativa cuando se mide de la terminal posi- tiva (+) a la negativa (−). La diferencia de potencial eléctrico en una resistencia (deno- tada mediante V), depende de la corriente que fluye por ella y de la resistencia que ofrece y está dada por la ley de Ohm: V = ± I R. El signo negativo (−) se usa cuando la diferencia en la resistencia se mide en dirección del flujo de corriente, y se utiliza el signo positivo (+) cuando la diferencia en la resis- tencia se mide en dirección opuesta al flujo de corriente. Todos los circuitos eléctricos constan de ciclos de voltaje y nodos de corriente. Un ciclo de voltaje es una conexión cerrada dentro del circuito. Por ejemplo, la figura 2.20 contiene los tres ciclos de voltaje a → b → c → f → a, c→d→e→f→c y a → b → c → d → e → f → a. Un nodo de corriente es un punto donde se encuentran tres o más segmentos de cable. Por ejemplo, la figura 2.20 contiene dos nodos de corriente en los puntos c y f. Los puntos, a, b, d y e no son nodos de corriente, pues en ellos sólo se encuentran dos segmentos de cable. Las leyes físicas que gobiernan el flujo de corriente en un circuito eléctrico son la conservación de la energía y la conservación de la carga. • La conservación de la energía se establece en un resultado conocido como ley de voltaje de Kirchhoff: en torno de cualquier ciclo de voltaje, la diferencia total de potencial eléctrico es igual a cero. • La conservación de la carga se establece en un resultado que se conoce como ley de corriente de Kirchhoff: en cualquier nodo de corriente, el flujo de todas las co- rrientes que llegan al nodo es igual al flujo de todas las corrientes que salen del no- do. Esto garantiza que la carga en un nodo no aumenta ni disminuye, de modo que el flujo de corriente es estacionario a lo largo del nodo.

146 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) EJEMPLO 1 Ahora podemos aplicar estas ideas, y los métodos para resolver sistemas lineales, a la resolución de problemas relacionados con los circuitos eléctricos. Estos problemas tienen el siguiente formato general: en un circuito con baterías, resistencias y cables, determinar todos los valores desconocidos de la diferencia de potencial eléctrico en las baterías, de las resistencias y de las corrientes, dados algunos valores, suficientes para calcular los valores desconocidos. El siguiente ejemplo ilustra lo dicho en el párrafo an- terior, para un caso en el cual las incógnitas son las corrientes. La figura 2.21 muestra el circuito de la figura 2.20, en el que las baterías tienen los po- tenciales eléctricos indicados, medidos de la terminal negativa a la positiva, y las resisten- cias tienen los valores señalados. El problema consiste en determinar las corrientes que fluyen por cada segmento del circuito. Figura 2.21 ᭤ b c d I R! =  I! R = # E =  8 E! = & 8 I R =  E = \" 8 R\" = ! af e Primero asignamos incógnitas para las corrientes en cada segmento del circuito que comienza en cierto nodo y termina en algún otro (sin nodos intermedios). Por ejem- plo, en la figura 2.21, asignamos I1 al segmento f → a → b → c, I2 al segmento f → c, e I3 al segmento c → d → e → f. Además, asignamos direcciones arbitrarias a estas corrientes, como indican las flechas de la figura 2.21. Si la dirección asignada es co- rrecta, el valor de corriente que se obtenga será positivo; si es incorrecta, el valor de corriente será negativo. Este último caso indica, por lo tanto, que la dirección real del flujo de corriente es justamente la opuesta a la asignada originalmente. Utilizando la ley de la corriente de Kirchhoff (la suma de las corrientes de entrada es igual a la suma de las corrientes de salida) en los puntos c y f, tenemos I1 + I2 = I3 e I3 = I1 + I2, (1) respectivamente. Como estas dos ecuaciones contienen la misma información, sólo ne- cesitamos una de ellas. En general, si un circuito tiene n nodos, la ley de la corriente de Kirchhoff proporcionará n − 1 ecuaciones útiles y una ecuación que es una combina- ción lineal de las otras n − 1. A continuación nos valemos de la ley de voltaje de Kirchhoff. Partimos del punto a y nos movemos por la batería de (−) a (+) hasta el punto b, de modo que la diferen- cia de potencial es +40 V. Al ir del punto b al punto c por la resistencia de 5 , se tie- ne una diferencia de potencial de −5I1. Al ir del punto c al punto f por la batería de 120 V y una resistencia de 10 se tiene una diferencia de potencial de −120 V (a lo largo de la batería) y una diferencia de potencial de +10I2 (a través de la resistencia). Por últi- mo al ir del punto f al punto a no hay diferencia de potencial. En resumen, al aplicar la ley de voltaje de Kirchhoff en el ciclo a → b → c → f → a, obtenemos

Sec. 2.4 Circuitos eléctricos 147 (+E1) + (−R1I1) + (−E2) + (+R2I2) = 0 o (+40) + (−5I1) + (−120) + (10I2) = 0, es decir, I1 − 2I2 = −16. (2) De manera análoga, al aplicar la ley de voltaje de Kirchhoff en el ciclo c → d → e → f → c, obtenemos (− R3I3) + (+E3) + (−R4I3) + (−R2I2) + (+E2) = 0 o (−20I3) + (+80) + (−30I3) + (−10I2) + (+120) = 0. Esto se simplifica a 10I2 + 50I3 = 200, o I2 + 5I3 = 20. (3) Observe que la ecuación resultante del ciclo de voltaje a → b → c → d → e → f → a se convierte en (+E1) + (−R1I1) + (−R3I3) + (+E3) + (−R4I3) = 0 o (+40) + (−5I1) + (−20I3) + (+80) + (−30I3) = 0, lo cual se simplifica a I1 + 10I3 = 24. Pero esta ecuación es justamente la combinación lineal Ecuación (2) + 2 Ecuación (3) y, por lo tanto, no proporciona nueva información; en consecuencia, es redundante y se puede omitir. En general, un ciclo exterior mayor, como a → b → c → d → e → f → a no proporciona nueva información si todos sus ciclos interiores, como a → b → c → f → a y c → d → e → f → c, ya han sido incluidos. Las ecuaciones (1), (2) y (3) conducen al sistema lineal ⎡ ⎤⎡ ⎤ ⎡ ⎤ 1 1 −1 I1 0 ⎣1 −2 0⎦ ⎣I2⎦ = ⎣−16⎦ . 0 1 5 I3 20 Al resolver para I1, I2 e I3 obtenemos (verifique) I1 = −3.5 A, I2 = 6.25 A e I3 = 2.75 A. El valor negativo de I1 indica que su verdadera dirección es la opuesta a la que se le asignó en la figura 2.21. ■ En general, en el caso de un circuito eléctrico que consta de baterías, resistencias y cables, y que tiene n diferentes asignaciones de corriente, las leyes de voltaje y corrien- te de Kirchhoff siempre conducen a n ecuaciones lineales que tienen una única solución. Términos clave Nodo de corriente Ley de voltaje de Kirchhoff Batería (pila) Ley de corriente de Kirchhoff Resistencia Cable Ciclo de voltaje

148 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) 2.4 Ejercicios En los ejercicios 1 a 4, determine las corrientes desconocidas En los ejercicios 5 a 8, determine los valores desconocidos en el en el circuito dado. circuito dado. 1. ! c \" I\" d 5. ! b c I b a I  8 I!  8 $ 8 & 8 E I ! ) d I# f e a e  I ! ! 8 2. Ic I\" d 6. I c  ) d  \" 8 b a# b e I! I  8 # $ E E! R 8 h !) I! e I I# g #) f a f 3. 7. b I c  I! d c R &) I d   8 I\" b E I\" I \" \" \") ! I! e a e f  8 I5 a f I 4. 8. a I b I\" c c I d & e # 4Ω ' ) f E d b I! # ) h # 8 I E  ! 8 I I# I\" g f a ! e I! #

Sec. 2.5 Cadenas de Markov 149 Ejercicios teóricos T.1. Para el siguiente circuito, demuestre que T.2. Para el siguiente circuito, demuestre que I1 = R2 I= R I I1 = R I, I2 = R I, R1 + R2 R1 R1 R2 e e I2 = R1 I= R I, I3 = R I, R1 + R2 R2 R3 donde donde 1 = 1 + 1 1 = 1 + 1 + 1 R R1 R2 . R R1 R2 R3 . a I bI c a Ib c d E R R E R R R! h I I I f I! fd g e 2.5 CADENAS DE MARKOV* Requisitos. Lectura de la sección 1.6, Soluciones de sistemas de ecuaciones lineales; manejo de conceptos básicos de probabilidad; conocimiento del concepto de límite. Consideremos un sistema que está, en cualquier momento dado, en uno y sólo un esta- do entre una cantidad finita de ellos. Por ejemplo, el clima en cierta área puede ser llu- vioso o despejado; una persona puede fumar o no fumar; vamos o no vamos a la escuela; vivimos en un área urbana, suburbana o rural; contamos con un nivel de ingre- sos bajo, medio o alto; compramos un automóvil Chevrolet, Ford o de alguna otra mar- ca. Al pasar el tiempo, el sistema puede pasar de un estado a otro, y supondremos que el estado del sistema es observado a periodos fijos (digamos, cada día, cada hora, etcé- tera). En muchas aplicaciones conocemos el estado actual del sistema y queremos pre- decir el que tendrá en el siguiente periodo de observación, o en cualquier otro. Con frecuencia podemos predecir, a partir de datos históricos, la probabilidad de que el sis- tema esté en cierto estado particular en determinado periodo de observación. Las apli- caciones que analizaremos a continuación son de este tipo. DEFINICIÓN Una cadena de Markov o proceso de Markov es aquel en el que la probabilidad de que el sistema esté en un estado particular en un periodo de observación dado, depen- de solamente de su estado en el periodo de observación inmediato anterior. Supongamos que el sistema tiene n estados posibles. Para cada i = 1, 2, . . . , n, y cada j = 1, 2, . . . , n, sea tij la probabilidad de que si el sistema se encuentra en el es- *Andrei Andreevitch Markov (1856-1922) pasó la mayor parte de su vida en San Petersburgo, ya que su pa- dre trabajaba en el departamento ruso de silvicultura. Fue estudiante y luego profesor en la Universidad de San Petersburgo. Político liberal, participó en las protestas contra el régimen zarista en la primera década del siglo XX. Aunque estaba interesado en muchos aspectos del análisis matemático, su trabajo más importante fue contribuir a establecer las bases de la teoría moderna de la probabilidad. Sus ideas, que darían lugar a lo que hoy conocemos como procesos de Markov, fueron motivadas por el deseo de dar una demostración rigu- rosa de la ley de los grandes números, y ampliar el campo de aplicaciones de esta ley. Tales ideas fueron pu- blicadas en una serie de artículos entre 1906 y 1912.

150 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) tado j en cierto periodo de observación, estará en el estado i en el siguiente; tij recibe el nombre de probabilidad de transición. Además, tij se aplica a cada periodo; es de- cir, no cambia con el tiempo. Como tij es una probabilidad, debemos tener que 0 ≤ tij ≤ 1 (1 ≤ i, j ≤ n). Asimismo, si el sistema está en el estado j en cierto periodo de observación, entonces debe estar en alguno de los n estados (ya que también podría permanecer en el estado j) en el siguiente. Por lo tanto, tenemos t1j + t2j + · · · + tnj = 1. (1) Es conveniente disponer las probabilidades de transición como la matriz T = [tij] de n × n, llamada matriz de transición de la cadena de Markov. Otros nombres para una matriz de transición son matriz de Markov, matriz estocástica y matriz de pro- babilidades. Como podemos ver, las entradas en cada columna de T son no negativas y, de acuerdo con la ecuación (1), suman 1. EJEMPLO 1 Supongamos que el clima de cierta ciudad es lluvioso o despejado. Como resultado de un EJEMPLO 2 amplio registro, se ha determinado que la probabilidad de que se dé un día lluvioso des- pués de un día despejado es 1 , y la probabilidad de que se tenga un día lluvioso después 3 de otro día lluvioso es 1 . Sea D el estado de un día despejado y R el de un día lluvioso. 2 Entonces, la matriz de transición de esta cadena de Markov es D R T= 2 1 D 3 2 1 3 1 R ■ 2 El ejemplo 9 de la sección 1.4 presenta una situación similar a la del ejemplo 2, que presentamos a continuación. Una empresa dedicada a la investigación de mercados está analizando un gran grupo de consumidores de café, que compran una lata de café cada semana. Se ha determinado que 50% de las personas que actualmente utilizan la marca A, la comprarán de nuevo la próxima semana, 25% cambiará a la marca B y 25% preferirá alguna otra. De las per- sonas que ahora consumen la marca B, 30% la comprará otra vez la próxima semana, 60% optará por la marca A y 10% cambiará a otra. De los consumidores que actualmente compran otra marca, 30% adquirirá de nuevo otra marcala próxima semana, 40% esco- gerá la marca A y 30% cambiará a la marca B. Los estados A, B y D representan la mar- ca A, la marca B y otra marca, respectivamente. La probabilidad de que una persona que consume la marca A cambie a la marca B es 0.25; la probabilidad de que una persona que consume la marca B la siga comprando es 0.3, y así sucesivamente. Por lo tanto, la matriz de transición de esta cadena de Markov es ⎡A B D⎤ T = ⎢⎢⎣00..2550 0.60 00..3400⎥⎥⎦ A 0.30 B 0.25 0.10 0.30 D ■ Ahora utilizaremos la matriz de transición del proceso de Markov para determinar la probabilidad de que el sistema se encuentre en cualquiera de los n estados en el futuro.

Sec. 2.5 Cadenas de Markov 151 Sea ⎡⎤ p1(k) x(k) = ⎢⎣⎢⎢⎢⎢⎢ ⎥⎥⎦⎥⎥⎥⎥ (k ≥ 0) p2(k) ... pn(k) el vector de estado del proceso de Markov en el periodo de observación k, donde p(jk) es la probabilidad de que el sistema se encuentre en el estado j en el periodo de obser- vación k. Al vector x(0), que denota el vector de estado en el periodo 0, se le llama vec- tor de estado inicial. El siguiente teorema, cuya demostración omitimos, se demuestra utilizando con- ceptos básicos de la teoría de probabilidad. TEOREMA 2.4 Si T es la matriz de transición de un proceso de Markov, el vector de estado x(k+1), en el (k + 1)-ésimo periodo de observación, puede determinarse a partir del vector de es- tado x(k) en el k-ésimo periodo de observación, como x(k+1) = Tx(k). (2) ■ La ecuación (2) indica que para obtener el vector de estado en el periodo (k+1) se mul- tiplica la matriz de transición por el vector de estado en el periodo k. De acuerdo con lo anterior, x(1) = T x(0) x(2) = T x(1) = T (T x(0)) = T 2x(0) x(3) = T x(2) = T (T 2x(0)) = T 3x(0), y, en general, que x(n) = T nx(0). Esto es, la matriz de transición y el vector de estado inicial determinan por completo to- dos los demás vectores de estado. EJEMPLO 3 Considere de nuevo el ejemplo 1. Suponga que comenzamos nuestra observación (día 0) en un día despejado, de modo que el vector de estado inicial es x(0) = 1 . 0 Entonces, el vector de estado en el día 1 (el día siguiente al que comenzamos nuestras observaciones) es x(1) = T x(0) = 0.67 0.5 1 = 0.67 , 0.33 0.5 0 0.33 donde las fracciones se han aproximado a dos decimales. Así, la probabilidad de que no llueva el día 1 es 0.67, y la probabilidad de que llueva ese día es 0.33. De manera similar, x(2) = T x(1) = 0.67 0.5 0.67 = 0.614 0.33 0.5 0.33 0.386 x(3) = T x(2) = 0.67 0.5 0.614 = 0.604 0.33 0.5 0.386 0.396 x(4) = T x(3) = 0.67 0.5 0.604 = 0.603 0.33 0.5 0.396 0.397 x(5) = T x(4) = 0.67 0.5 0.603 = 0.603 . 0.33 0.5 0.397 0.397

152 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) A partir del cuarto día, el vector de estado del sistema es siempre el mismo, 0.603 . 0.397 Esto significa que, a partir del cuarto día, no llueve en 60% del tiempo, y llueve 40% del tiempo. ■ EJEMPLO 4 Consideremos de nuevo el ejemplo 2. Suponga que al iniciar el estudio vemos que la marca A tiene 20% del mercado, la marca B tiene 20% del mismo y las otras marcas tienen el 60% restante. Entonces, el vector de estado inicial x(0) es, ⎡⎤ 0.2 x(0) = ⎣0.2⎦ . 0.6 El vector de estado después de la primera semana es ⎡ ⎤⎡ ⎤ ⎡ ⎤ 0.50 0.60 0.40 0.2 0.4600 x(1) = T x(0) = ⎣0.25 0.30 0.30⎦ ⎣0.2⎦ = ⎣0.2900⎦ . 0.25 0.10 0.30 0.6 0.2500 De manera análoga, ⎡ ⎤⎡ ⎤ ⎡ ⎤ 0.50 0.60 0.40 0.4600 0.5040 x(2) = T x(1) = ⎣0.25 0.30 0.30⎦ ⎣0.2900⎦= ⎣0.2770⎦ 0.25 0.10 0.30 0.2500 0.2190 ⎡ ⎤⎡ ⎤ ⎡ ⎤ 0.50 0.60 0.40 0.5040 0.5058 x(3) = T x(2) = ⎣0.25 0.30 0.30⎦ ⎣0.2770⎦= ⎣0.2748⎦ 0.25 0.10 0.30 0.2190 0.2194 ⎡ ⎤⎡ ⎤ ⎡ ⎤ 0.50 0.60 0.40 0.5058 0.5055 x(4) = T x(3) = ⎣0.25 0.30 0.30⎦ ⎣0.2748⎦= ⎣0.2747⎦ 0.25 0.10 0.30 0.2194 0.2198 ⎡ ⎤⎡ ⎤ ⎡ ⎤ 0.50 0.60 0.40 0.5055 0.5055 x(5) = T x(4) = ⎣0.25 0.30 0.30⎦ ⎣0.2747⎦= ⎣0.2747⎦ . 0.25 0.10 0.30 0.2198 0.2198 En consecuencia, cuando n crece, los vectores de estado tienden al vector fijo ⎡⎤ 0.5055 ⎣0.2747⎦ . 0.2198 Esto significa que, a largo plazo, la marca A tendrá el control de cerca de 51% del mer- cado, la marca B dominará más o menos 27% del mismo y las otras marcas tendrán la predilección del 22% restante. ■ En los dos últimos ejemplos hemos visto que los vectores de estado convergen a un vector fijo cuando el número de periodos de observación aumenta. En este caso deci- mos que el proceso de Markov ha alcanzado el equilibrio. El vector fijo es el vector de estado estacionario. Los procesos de Markov se utilizan por lo general para determi- nar el comportamiento de un sistema a largo plazo; por ejemplo, la parte del mercado que cierto fabricante espera conservar de manera más o menos permanente. Por lo tan- to, saber si un proceso de Markov alcanza o no el equilibrio es de particular importan- cia. El siguiente ejemplo muestra que no todos los procesos de Markov alcanzan el equilibrio.

Sec. 2.5 Cadenas de Markov 153 EJEMPLO 5 Sean T= 0 1 ⎡⎤ 1 0 1 y x(0) = ⎣ 3 ⎦ . 2 3 Entonces, ⎡⎤ ⎡⎤ ⎡⎤ ⎡⎤ 2 1 2 1 x(1) = ⎣ 3 ⎦ , x(2) = ⎣ 3 ⎦ , x(3) = ⎣ 3 ⎦ , x(4) = ⎣ 3 ⎦ , . . . . 1 2 1 2 3 3 3 3 Por lo tanto, los vectores de estado oscilan entre los vectores ⎡⎤ y ⎡⎤ 2 1 ⎣3⎦ ⎣3⎦, 1 2 3 3 y no convergen a un vector fijo. ■ Sin embargo, si pedimos que la matriz de transición de un proceso de Markov sa- tisfaga una propiedad razonable, obtenemos una amplia clase de procesos de Markov, muchos de los cuales surgen en aplicaciones prácticas, que realmente alcanzan el equi- librio. A continuación formularemos con precisión estas ideas. DEFINICIÓN El vector ⎡u1⎤ u = ⎢⎣⎢u...2⎥⎥⎦ un es un vector de probabilidad si ui ≥ 0 (1 ≤ i ≤ n) y u1 + u2 + · · · + un = 1. EJEMPLO 6 Los vectores ⎡⎤ ⎡⎤ 11 ⎢⎣⎢ 2 ⎥⎥⎦ y ⎢⎣⎢ 3 ⎦⎥⎥ 1 2 4 3 1 0 4 son vectores de probabilidad; los vectores ⎡⎤ ⎡⎤ 1 1 ⎢⎣⎢ 5 ⎦⎥⎥ y ⎢⎣⎢ 3 ⎦⎥⎥ 1 1 5 2 2 1 2 5 no son vectores de probabilidad. (¿Por qué no?) ■ DEFINICIÓN Una matriz de transición T de un proceso de Markov es regular si todas las entradas de alguna potencia de T son positivas. Un proceso de Markov es regular si su matriz de transición es regular.

154 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) En los ejemplos 1 y 2, los procesos de Markov son regulares, pues todas las entra- das de las propias matrices de transición son positivas. EJEMPLO 7 La matriz de transición T= 0.2 1 es regular, ya que 0.8 0 T2 = 0.84 0.2 . 0.16 0.8 ■ Establecemos ahora el siguiente teorema fundamental de los procesos de Markov regulares; la demostración, que omitimos, puede consultarse en el libro de Kemeny y Snell que se cita en la bibliografía recomendada al final de la sección. TEOREMA 2.5 Si T es la matriz de transición de un proceso de Markov regular, entonces (a) A medida que n → ∞, T n tiende a una matriz ⎡u1 u1 ··· u ⎤ 1 A = ⎢⎢⎣u...2 u2 · · · u...2⎥⎥⎦ , ... un un · · · un tal que todas sus columnas son idénticas. (b) Toda columna ⎡u1⎤ u = ⎢⎢⎣u...2⎦⎥⎥ un de A es un vector de probabilidad tal que todos sus componentes son positivos. Es decir, ui > 0 (1 ≤ i ≤ n) y u1 + u2 + · · · + un = 1. ■ A continuación establecemos el siguiente resultado. TEOREMA 2.6 Si T es una matriz de transición regular y A y u son como en el teorema 2.5, entonces: (a) Para cualquier vector de probabilidad x, T nx → u conforme n → ∞, de modo que u es un vector de estado estacionario. (b) El vector de estado estacionario u es el único vector de probabilidad que satisfa- ce la ecuación matricial Tu = u. Demostración (a) Sea ⎡x1⎤ x = ⎣⎢⎢x...2⎥⎥⎦ xn un vector de probabilidad. Como T n → A a medida que n → ∞, tenemos T nx → Ax.

Sec. 2.5 Cadenas de Markov 155 Ahora, ⎡u1 u1 · · · u1⎤ ⎡x1⎤ ⎡u1x1 + u1x2 + · · · + u1xn ⎤ Ax = ⎢⎢⎣u...2 u2 ··· u2 ⎦⎥⎥ ⎣⎢⎢x...2⎥⎥⎦ = ⎢⎢⎣ u 2 x1 + u2x2 + · · · + u2xn ⎦⎥⎥ ... ... ... un un · · · un xn unx1 + unx2 + · · · + unxn ⎡u1(x1 + x2 + · · · + xn)⎤ ⎡u1⎤ = ⎢⎢⎣u2(x1 + x2 + · · · + xn )⎥⎥⎦ = ⎣⎢⎢u...2⎦⎥⎥ , ... un(x1 + x2 + · · · + xn) un pues x1 + x2 + · · · + xn = 1. Por lo tanto, T n x → u. (b) Como T n → A, también tenemos que T n+1 → A. Sin embargo, T n+1 = T T n, de modo que T n+1 → TA. En consecuencia, TA = A. Al igualar las columnas correspondientes de esta ecuación (utilizando el ejercicio T.9 de la sección 1.3), te- nemos que Tu = u. Para demostrar que u es único, sea v otro vector de probabili- dad tal que Tv = v. De acuerdo con (a), T nv → u, y como Tv = v, tenemos que T nv = v para todo n. Por lo tanto v = u. ■ En los ejemplos 3 y 4 obtuvimos los vectores de estado estacionario calculando las potencias T nx. Otra forma de calcular el vector de estado estacionario de una matriz de transición regular es el siguiente. Según (b) del teorema 2.6, podemos escribir Tu = u como Tu = Inu o (In − T)u = 0. (3) Hemos demostrado que el sistema homogéneo (3) tiene una única solución u que es un vector de probabilidad, de modo que u1 + u2 + · · · + un = 1. (4) El primer procedimiento para calcular el vector de estado estacionario u de una ma- triz de transición regular T es el siguiente. Paso 1. Calculamos las potencias T nx, donde x es cualquier vector de probabilidad. Paso 2. u es el límite de las potencias T nx. El segundo procedimiento para calcular el vector de estado estacionario u de una matriz de transición regular T es el siguiente. Paso 1. Resolvemos el sistema homogéneo (In – T)u = 0.* Paso 2. De la infinidad de soluciones obtenidas en el paso 1, determinamos una úni- ca solución u, al exigir que sus componentes satisfagan la ecuación (4). *Este tipo de problemas se estudiará con mayor profundidad en el capítulo 8.

156 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) EJEMPLO 8 Consideremos la matriz del ejemplo 2. El sistema homogéneo (3) es (verifique) ⎡ −0.60 ⎤⎡ ⎤ ⎡ ⎤ 0.50 −0.40 u1 0 0.70 −0.30⎦ ⎣u2⎦ = ⎣0⎦ . ⎣−0.25 −0.10 −0.25 0.70 u3 0 La forma escalonada reducida por filas de la matriz aumentada es (verifique) ⎡⎤ 1 0 −2.30 0 ⎣0 1 −1.25 0⎦ . 0 0 0.00 0 Por lo tanto, una solución es u1 = 2.3r u2 = 1.25r u3 = r, donde r es cualquier número real. Con base en la ecuación (4), tenemos 2.3r + 1.25r + r = 1, o bien, r = 1 ≈ 0.2198. 4.55 Por lo tanto, u1 = 0.5055 u2 = 0.2747 u3 = 0.2198. Estos resultados coinciden con los que se obtuvieron en el ejemplo 4. ■ Lecturas adicionales KEMENY, JOHN G. y J. LAURIE SNELL, Finite Markov Chains, Nueva York, Springer-Ver- lag, 1976. MAKI, D.P. y M. THOMPSON, Mathematical Models and Applications: With Emphasis on the Social, Life, and Management Sciences, Upper Saddle River, Nueva Jersey, Prenti- ce Hall, 1973. ROBERTS, FRED S., Discrete Mathematical Models with Applications to Social, Biologi- cal, and Enviromental Problems, Upper Saddle River, Nueva Jersey, Prentice Hall, 1997. Términos clave Vector de estado Vector de estado inicial Cadena de Markov (o proceso de Markov) Vector de estado estacionario Probabilidad de transición Equilibrio Matriz de transición (matriz de Markov, matriz estocástica o matriz de probabilidades)

Sec. 2.5 Cadenas de Markov 157 2.5 Ejercicios 1. ¿Cuáles de las siguientes pueden ser matrices de transición ⎡ ⎤⎡ ⎤ 1 1 3 1 1 3 0 5 de un proceso de Markov? (a) ⎢⎢⎣0 1⎥⎦⎥ ⎢⎣⎢ 4 02 ⎥⎥⎦ 1 0 ⎡⎤ 3 (b) 1 0.2 0.3 0.1 2 (a) 0.3 0.7 (b) ⎣0.8 0.5 0.7⎦ 0 1 0 121 0.4 0.6 3 452 0.0 0.2 0.2 8. Demuestre que cada una de las siguientes matrices de tran- ⎡⎤ (c) 0.55 0.33 0.3 0.4 0.2 sición alcanza un estado de equilibrio. 0.45 0.67 (d) ⎣0.2 0.0 0.8⎦ ⎡⎤ 0.1 0.3 0.6 1 1⎦ 0.4 0.2 0 (b) 0.6 0.8 (a) ⎣ 2 1 2. ¿Cuáles de los siguientes son vectores de probabilidad? 2 ⎡⎤ ⎡⎤ ⎡ 1 ⎤ ⎡ ⎤ 0.3 0.4 ⎡⎤ 1 1 1 1 0.1 0.0⎦ 0 (d) ⎣0.2 0.4 1 ⎡⎤ ⎢⎢⎢⎢⎢⎣ 4 ⎥⎥⎥⎥⎦⎥ ⎢⎢⎢⎢⎢⎣ 5 ⎥⎥⎥⎥⎥⎦ ⎢⎢⎣ 3 2 ⎥⎦⎥ 0.6 0 ⎣⎢⎢ 2 ⎥⎥⎦ 1 2 (c) 1 1 (b) ⎣1⎦ 6 5 3 4 (a) 1 (c) (d) 3 0 1 1 1 1 0.5 0.5 3 10 3 0 4 2 3 12 ⎡ ⎤ 4 10 9. Sea 1 0⎦ . 1 En los ejercicios 3 y 4, determine un valor para cada entrada T = ⎣2 faltante, denotada por ᮀ, de modo que la matriz sea la matriz 1 de transición de una cadena de Markov. En algunos casos puede 2 haber más de una respuesta correcta. (a) Demuestre que T no es regular. ⎡ ⎤⎡ ⎤ (b) Demuestre que T nx → 0 0.4 0.3 0.2 0.1 0.3 1 3. ⎣0.3 0.5⎦ 4. ⎣0.3 0.5⎦ para cualquier vector de 0.2 probabilidad x. En consecuencia, una cadena de Mar- kov puede tener un único vector de estado estacionario, 5. Considere la matriz de transición aunque su matriz de transición no es regular. T= 0.7 0.4 . 10. Determine el vector de estado estacionario para cada una 0.3 0.6 de las siguientes matrices regulares. ⎡⎤ 1 1 1 (b) 0.3 0.1 0 (a) Si x(0) = , calcule x(1), x(2) y x(3) con tres cifras (a) ⎣ 3 2⎦ 1 0.7 0.9 2 decimales. 3 2 (b) Demuestre que T es regular y encuentre su vector de ⎡ 1 ⎤ ⎡ ⎤ 0.1 11 0.4 0.0 0.3⎦ (d) ⎣0.2 0.5 estado estacionario. (c) ⎢⎢⎣ 4 2 3 ⎥⎥⎦ 0.6 0 1 2 2 3 6. Considere la matriz de transición 3 00 0.4 0.5 4 ⎡ ⎤ 0 0.2 0.0 11. (Psicología) Un psicólogo del comportamiento coloca to- 0.3 0.3⎦ . dos los días una rata en una jaula con dos puertas, A y B. T = ⎣0 La rata puede pasar por la puerta A, en cuyo caso recibirá 0.7 un choque eléctrico, o por la puerta B, con lo cual obtiene 1 0.5 cierto alimento. Se registra la puerta por la que pasa la rata. Al inicio del experimento, un lunes, la rata tiene la misma (a) Si ⎡⎤ probabilidad de pasar por la puerta A que por la puerta B. 0 Después de pasar por la puerta A y recibir una descarga eléctrica, la probabilidad de volver a pasar por la misma x(0) = ⎣1⎦ , puerta al día siguiente es 0.3. Después de pasar por la puer- ta B y recibir alimento, la probabilidad de pasar por la mis- 0 ma puerta al día siguiente es 0.6. calcule x(1), x(2) y x(3) con tres cifras decimales. (a) Escriba la matriz de transición para el proceso de Markov. (b) Demuestre que T es regular y encuentre su vector de (b) ¿Cuál es la probabilidad de que la rata vuelva a pasar estado estacionario. por la puerta A el jueves (el tercer día después del ini- cio del experimento)? 7. ¿Cuáles de las siguientes matrices de transición son regulares? (c) ¿Cuál es el vector de estado estacionario? ⎡ ⎤ ⎡ 1 ⎤ (a) ⎣0 1 ⎢⎢⎣ 2 0 0 ⎥⎥⎦ 1 1 2⎦ (b) 0 0 1 2 1 1 1 2 2 2

158 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) 12. (Negocios) El departamento de suscripciones de una revis- RW y WW. Al cruzar cada uno de estos genotipos con un ta envía cartas a una enorme lista de correos, invitando a genotipo RW, obtenemos la matriz de transición los destinatarios a suscribirse. Algunas de las personas que recibieron la carta ya estaban suscritas, y otras no. De la Flores de la Flores de la planta madre lista de correo, 60% de las personas ya suscritas se suscri- planta hija birán de nuevo, mientras que 25% de las no suscritas lo harán. ⎡ R P W⎤ R 0.5 0.25 0.0 (a) Escriba la matriz de transición para este proceso de P ⎣0.5 0.50 0.5⎦. Markov. W 0.0 0.25 0.5 (b) Al enviarse la última carta, se determinó que 40% de Suponga que cada generación posterior se produce cruzan- quienes la recibieron ordenaron una suscripción. ¿Qué do sólo con plantas del genotipo RW. ¿En qué momento porcentaje de las personas que reciben la carta actual alcanza el equilibrio el proceso?, ¿qué porcentaje de las se espera que pidan una suscripción? plantas será de flores rojas, rosadas o blancas? 13. (Sociología) Un estudio ha determinado que la ocupación 15. (Transporte colectivo) Un sistema de transporte colectivo de un niño, cuando sea adulto, depende de la ocupación de su padre y está dada por la siguiente matriz de transición, entra en operación. Las autoridades de tránsito han realiza- donde P = profesional, F = agricultor y L = obrero. do estudios que predicen el porcentaje de quienes utilizarán el sistema colectivo (M) y el de las personas que seguirán Ocupación del padre manejando su auto (A). Se ha obtenido la siguiente matriz ⎡P F L⎤ de transición: P 0.8 0.3 0.2 Ocupación F ⎣0.1 0.5 0.2⎦ Año actual del hijo L 0.1 0.2 0.6 M A Año siguiente M 0.7 0.2 . A 0.3 0.8 En consecuencia, la probabilidad de que el hijo de un profe- sional también sea un profesional es 0.8, y así sucesivamente. Suponga que la población del área permanece constante y que al principio 30% de la gente se traslada en el transporte (a) ¿Cuál es la probabilidad de que el nieto de un profesio- colectivo y 70% en automóvil. nal también sea un profesional? (a) ¿Qué porcentaje utilizará el sistema de transporte co- (b) A largo plazo, ¿qué proporción de la población se dedi- lectivo después de un año? ¿Después de dos años? cará a la agricultura? (b) ¿En el largo plazo, ¿qué porcentaje empleará el sistema 14. (Genética) Considere una planta que puede tener flores ro- de transporte colectivo? jas (R), rosadas (P) o blancas (W), según los genotipos RR, Ejercicio teórico T.1. ¿La transpuesta de una matriz de transición de una cadena de Markov, también es una matriz de transición de una cadena de Markov? Explique. Ejercicios con MATLAB ML.3. En MATLAB, escriba help sum y determine la acción del comando sum en una matriz de m × n. Aplique el El cálculo de la sucesión de vectores x(1), x(2), . . . , como en los comando sum para determinar cuáles de las siguientes ejemplos 3 y 4, se puede realizar fácilmente mediante ciertos son matrices de Markov. comandos de MATLAB. Una vez que la matriz de transición T y el vector de estado inicial x(0) se introducen a MATLAB, el vector ⎡⎤ de estado del k-ésimo periodo de observación se obtiene me- diante el comando 211 T∧k ∗ x (a) ⎢⎣⎢ 3 3 2 ⎥⎥⎦ ML.1. Utilice MATLAB para verificar los cálculos de los vecto- 1 1 1 res de estado del ejemplo 3, para los periodos de 1 a 5. 3 3 4 ML.2. En el ejemplo 4, si el estado inicial se cambia por 0 11 0.7⎤ ⎡⎤ 34 0.3⎦ 0.1 ⎡0.5 ⎣0.3⎦ , (b) ⎣0.3 0.6 0.6 0.2 determine x(5). 0.1 0.2 0.0 ⎡0.66 0.25 0.125⎤ (c) ⎣0.33 0.25 0.625⎦ 0.00 0.50 0.250

Sec. 2.6 Modelos económicos lineales 159 2.6 MODELOS ECONÓMICOS LINEALES Requisito. Lectura de la sección 1.7, La inversa de una matriz. A medida que la sociedad se ha hecho cada vez más compleja, la atención al análisis del comportamiento económico también ha ido aumentando. Por muchas razones, los problemas involucrados en dicho análisis son más difíciles de tratar que los de las cien- cias físicas. Por ejemplo, podría ocurrir que no conociéramos todos los factores o va- riables que deben considerarse, que no contáramos con todos los datos que deben reunirse o que ignoráramos cuándo se tiene suficiente información; también podría su- ceder que la resolución del problema matemático resultante fuera demasiado difícil. En la década de los treinta del siglo XX, Wassily Leontief, profesor de economía de la Universidad de Harvard, desarrolló uno de los primeros métodos de análisis matemá- tico del comportamiento económico. En 1973 recibió el premio Nobel de Economía por ese trabajo. En esta sección daremos una breve introducción a las aplicaciones del ál- gebra lineal a la economía. En gran medida, nuestro enfoque se basa en el material de los libros de Gale y de Johnston, Price y van Vleck, citados en las lecturas adicionales; el lector puede consul- tar estos libros para conocer el tema con más amplitud. MODELO CERRADO DE LEONTIEF EJEMPLO 1* Considere una sociedad sencilla, formada por un agricultor, un carpintero y un sastre. Cada uno produce un bien: el agricultor produce los alimentos, el carpintero construye las casas, y el sastre fabrica la ropa. Por conveniencia, hemos elegido nuestras unidades de modo que cada individuo produce una unidad de cada artículo durante el año. Su- ponga que durante un año, la parte de cada artículo que consume cada individuo está dada en la tabla 2.1. Tabla 2.1 Bienes Bienes producidos por: consumidos por: Agricultor Carpintero Sastre Agricultor Carpintero 7 1 3 Sastre 16 2 16 5 1 5 16 6 16 1 1 1 4 3 2 De acuerdo con lo anterior, el agricultor consume 7 de su propio producto, mientras 16 que el carpintero consume 5 del producto del agricultor, el carpintero consume 5 de 16 16 la ropa hecha por el sastre, etcétera. Sea p1 el precio por unidad de alimento, p2 el pre- cio por unidad de habitación y p3 el precio por unidad de vestido. Suponemos que ca- da uno de ellos paga el mismo precio por un artículo, de manera que el agricultor paga el mismo precio por su alimento que el sastre y el carpintero, aunque él lo haya produ- cido. Nos interesa determinar los precios p1, p2 y p3 de modo que haya un estado de equilibrio, el cual definimos como: nadie gana o pierde dinero. Los gastos del agricultor son 7 p1 + 1 p2 + 3 p3, 16 2 16 *Este ejemplo se cita en la obra de Johnston, Price y van Vleck que se indica en las lecturas adicionales. Tam- bién Gale presenta el modelo general para este ejemplo.

160 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) mientras que su ingreso es p1, pues él produce una unidad de alimento. Como los gas- tos deben igualar al ingreso, tenemos 7 p1 + 1 p2 + 3 p3 = p1. (1) 16 2 16 De manera análoga, en el caso del carpintero tenemos 5 p1 + 1 p2 + 5 p3 = p2, (2) 16 6 16 (3) (4) y en el del sastre tenemos 1 p1 + 1 p2 + 1 p3 = p3. 4 3 2 Las ecuaciones (1), (2) y (3) se pueden escribir en notación matricial como Ap = p, donde ⎡⎤ ⎡⎤ 713 p1 A = ⎢⎣⎢ 16 2 16 ⎦⎥⎥ , p = ⎣ p2⎦ . p3 5 1 5 16 6 16 11 1 43 2 Podemos rescribir la ecuación (4) como (In – A)p = 0 (5) que es un sistema homogéneo. Nuestro problema consiste en determinar una solución p para (5), cuyos compo- nentes pi sean no negativos, con al menos un pi positivo, pues p = 0 significaría que to- dos los precios son nulos, lo cual carece de sentido. Al resolver (5), obtenemos (verifique) ⎡⎤ 4 p = r ⎣3⎦ , 4 donde r es cualquier número real. Si r es un número positivo, determinamos los precios relativos de los artículos. Por ejemplo, si r = 1000, vemos que cada unidad de alimen- to cuesta $4,000, cada unidad de habitación cuesta $3,000 y cada unidad de vestido cuesta $4,000. ■ EJEMPLO 2 (Modelo de intercambio) Consideremos ahora el problema general en el que tenemos n fabricantes, M1, M2, . . . , Mn, y n artículos, G1, G2, . . . Gn, donde Mi sólo fabrica Gi. Consideremos un intervalo fijo, digamos un año, y supongamos que Mi sólo fabrica una unidad de Gi durante dicho periodo. Al producir el artículo Gi, el fabricante Mi puede consumir ciertas cantidades de los artículos G1, G2, . . . , Gi, . . . , Gn. Por ejemplo, el hierro, junto con otros ingredientes, sirve para fabricar acero. Sea aij la cantidad del artículo Gj consumida por el fabrican- te Mi. Entonces, 0 ≤ aij ≤ 1. Supongamos que el modelo es cerrado, es decir, ningún artículo entra o sale del siste- ma. Esto significa que el consumo total de cada artículo debe ser igual a su producción total. Como la producción total de Gj es 1, tenemos a1j + a2j + · · · + anj = 1 ( 1 ≤ j ≤ n).

Sec. 2.6 Modelos económicos lineales 161 Si el precio unitario de Gk es pk, entonces el fabricante Mi paga ai1p1 + ai2 p2 + · · · + ain pn (6) por los artículos que usa. Nuestro problema consiste en determinar los precios p1, p2, . . . , pn, de modo que ningún fabricante gane o pierda dinero, es decir, logrando que el ingreso de cada fabri- cante sea igual a sus gastos. Como Mi sólo fabrica una unidad, sus ingresos son iguales a pi. En consecuencia, de acuerdo con la ecuación (6), tenemos a11 p1 + a12 p2 + · · · + a1n pn = p1 a21 p1 + a22 p2 + · · · + a2n pn = p2 ... ... ... ... an1 p1 + an2 p2 + · · · + ann pn = pn, que puede escribirse en forma matricial como Ap = p, (7) donde ⎡ p1⎤ A = [aij] y p = ⎢⎣⎢ p2 ⎥⎥⎦ . ... pn Podemos rescribir la ecuación (7) como (8) (In − A)p = 0. ■ Por lo tanto, nuestro problema consiste en determinar un vector p ≥ 0, con al menos un componente positivo y que satisfaga la ecuación (8). DEFINICIÓN Una matriz A = [aij] de n × n es una matriz de intercambio si satisface las dos pro- piedades siguientes: (a) aij ≥ 0 (cada entrada es no negativa). (b) aij + a2j + · · · + anj = 1, para j = 1, 2, . . . , n (las entradas de cada columna su- man 1). EJEMPLO 3 La matriz A del ejemplo 1 es una matriz de intercambio, al igual que la matriz A del ejemplo 2. ■ Nuestro problema general se puede enunciar como sigue: dada una matriz de inter- cambio A, determinar un vector p ≥ 0, con al menos un componente positivo, que sa- tisfaga la ecuación (8). Puede demostrarse que este problema siempre tiene solución (vea la página 264 del libro de Gale que se cita en las lecturas adicionales). En nuestro problema general hemos pedido que el ingreso de cada fabricante sea igual a sus gastos, pero también podríamos pedir que los gastos de cada fabricante no sean mayores que su ingreso. Esto haría que Ap ≤ p (9)

162 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) en lugar de Ap = p. Sin embargo, puede demostrarse (ejercicio T.1) que si se cumple la ecuación (9), se cumplirá también la ecuación (7). De esta manera, si ningún fabri- cante gasta más de lo que gana, el ingreso de cada uno de ellos será igual a sus gastos. Una interpretación económica de esta afirmación es que, en el modelo cerrado de Leon- tief, si algún fabricante está logrando ganancias, al menos un fabricante está sufriendo pérdidas. UN MODELO DE COMERCIO INTERNACIONAL EJEMPLO 4 Suponga que n países, C1, C2, . . . , Cn, comercian entre sí y utilizan la misma moneda. Su- pongamos que los precios están fijos durante este análisis y que el ingreso de Cj, que denotamos mediante yj, proviene en su totalidad de la venta de sus productos, ya sea en el mercado interno o a los demás países. Supongamos también que la parte de su ingre- so que Cj gasta en importaciones de Ci es un número fijo aij, que no depende del ingreso yj de Cj. Como las aij son parte de yj, tenemos que aij ≥ 0 a1j + a2j + · · · + an j = 1, de modo que A = [aij] es una matriz de intercambio. Ahora queremos determinar el in- greso total yi de cada país Ci. Como el valor de las exportaciones de Ci a Cj es aij yj, el ingreso total de Ci es ai1 y1 + ai2 y2 + · · · + ain yn. Por lo tanto, debemos tener ai 1y1 + ai2 y2 + · · · + ain yn = yi. En notación matricial, debemos determinar ⎡ y1 ⎤ p = ⎢⎢⎣ y2 ⎥⎥⎦ ≥ 0, ... yn con al menos una yi > 0, de modo que Ap = p, que era nuestro problema anterior. ■ EL MODELO ABIERTO DE LEONTIEF Suponga que tenemos n artículos, G1, G2, . . . , Gn, y n actividades, M1, M2, . . . , Mn. Su- ponga que cada actividad Mi produce sólo un artículo Gi y que Gi es producido sólo por Mi. Sea cij ≥ 0 el valor monetario de Gi que debe consumirse para producir una canti- dad de Gj con valor de un dólar. La matriz C = [cij] es la matriz de consumo. Obser- ve que cii puede ser positivo, lo cual significa que podríamos necesitar cierta cantidad de Gi para producir una cantidad de Gi con valor de un dólar. Sea xi el valor en dólares de la cantidad de Gi producida en un periodo fijo, diga- mos, un año. El vector ⎡x1⎤ (xi ≥ 0) (10) x = ⎣⎢⎢x...2⎥⎦⎥ xn

Sec. 2.6 Modelos económicos lineales 163 es el vector de producción. La expresión ci1x1 + ci2x2 + · · · + cin xn es el valor total de la parte consumida del producto Gi, determinada por el vector de producción para elaborar una cantidad de G1 con valor de x1 dólares, una cantidad de G2 con valor de x2 dólares, etcétera. Observe que la expresión dada por la ecuación (10) es la i-ésima entrada del producto matricial Cx. La diferencia entre el valor en dó- lares de la cantidad producida de Gi y el valor total en dólares de la cantidad consumi- da de Gi, xi − (ci1x1 + ci2x2 + · · · + cinxn), (11) es la producción neta. Observe que la expresión en la ecuación (11) es la i-ésima entrada de x − Cx = (In − C)x. Ahora sea di el valor en dólares de la demanda externa de Gi, y sea ⎡d1⎤ d = ⎢⎢⎣d...2⎥⎥⎦ (di ≥ 0) dn el vector de demanda. Nuestro problema se puede enunciar de la manera siguiente: dado un vector de demanda d ≥ 0, ¿es posible determinar un vector de producción x tal que la demanda externa d se satisfaga sin un superávit? Es decir, ¿es posible determinar un vector x ≥ 0 que satisfaga la siguiente ecuación? (In − C)x = d. (12) EJEMPLO 5 Sea ⎡ ⎤ 1 1 C = ⎣4 2⎦ 2 1 3 3 una matriz de consumo. Entonces ⎡ ⎤⎡ ⎤ 1 0 1 13 − 1 0 1 2 I2 − C = − ⎣4 2⎦ = ⎣ 4 ⎦ . 2 1 − 2 2 3 3 3 3 La ecuación (12) se transforma en ⎡ ⎤ 3 − 1 ⎦ x1 = d1 , 2 x2 d2 ⎣4 − 2 2 3 3 de modo que ⎡ ⎤−1 ⎡ ⎤ x1 3 − 1 d1 = ⎣4 3⎦ d1 x2 2 d2 4 d2 =⎣ 4 ⎦ 9 ≥ 0, − 2 2 3 3 2 ya que d1 ≥ 0 y d2 ≥ 0. En consecuencia, podemos obtener un vector de producción pa- ra cualquier vector de demanda dado. ■

164 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) En general, si (In − C)−1 existe y es ≥ 0, entonces x = (In − C)−1d ≥ 0 es un vec- tor de producción para cualquier vector de demanda dado. Sin embargo, para una ma- triz de consumo dada, la ecuación (12) podría no tener solución. EJEMPLO 6 Considere la matriz de consumo DEFINICIÓN ⎡ ⎤ EJEMPLO 7 1 1 C = ⎣2 2⎦. 1 3 2 4 Entonces ⎡ ⎤ e 1 − 1 2 I2 − C = ⎣2 ⎦ − 1 1 2 4 ( I2 − C)−1 = −2 −4 , −4 −4 de modo que x = (I2 − C)−1d no es un vector de producción si d 0, pues todos sus componentes son negativos; por lo tanto, el problema no tiene solución. Si d = 0, sí tenemos una solución, a saber, x = 0, lo cual significa que si no hay demanda externa, no hay producción alguna. ■ Una matriz de consumo C de n × n es productiva si (In − C)−1 existe e (In − C)−1 ≥ 0. Es decir, C es productiva si (In − C) es no singular y todas las entradas de (In − C)−1 son no negativas. En este caso, el modelo también se llama productivo. De acuerdo con lo anterior, si C es productiva, entonces para cualquier vector de demanda d ≥ 0, la ecuación (In − C)x = d tiene una única solución, x ≥ 0. Considere la matriz de consumo ⎡ ⎤ 1 1 C = ⎣2 3⎦. 1 1 4 3 Entonces ⎡ ⎤ 1 − 1 3 ( I2 − C) = ⎣2 ⎦ , − 1 2 4 3 e ⎡⎤ 2 1 ( I2 − C )−1 = 4 ⎣3 3⎦. 1 1 42 En consecuencia, C es productiva. Si d ≥ 0 es un vector de demanda, la ecuación (In − C)x = d tiene la solución única x = (In − C)−1d ≥ 0. ■

Sec. 2.6 Modelos económicos lineales 165 Lecturas adicionales Algunos textos más avanzados (como el libro de Johnston citado en las lecturas adicionales, página 251) demuestran los criterios para decidir si una matriz de consu- mo dada es productiva. GALE, DAVID, The Theory of Linear Economic Models, Nueva York, McGraw-Hill Book Company, 1960. JOHSTON, B., G. PRICE y F.S. VAN VLECK, Linear Equations and Matrices, Reading, Massachusetts: Addison-Wesley Publishing Co., Inc., 1966. Términos clave Modelo abierto de Leontief Vector de demanda Matriz de consumo Matriz productiva Modelo cerrado de Leontief Vector de producción Modelo productivo Modelo de intercambio Producción neta Matriz de intercambio Modelo de comercio internacional 2.6 Ejercicios 1. ¿Cuáles de las siguientes son matrices de intercambio? yidmedpCeo1Crtq3auceeisogn-14-ae;ssqtadueeenClai1mferpasco-25-cr,tiaódcneioCdne2elseisndg-1e5-reyCs1doeedsCe-14-3C,e2dseq-25-uC;eq2gueaess-lt12-aa en ⎡ ⎤⎡ ⎤ fracción del ingreso de C3 que gasta en importaciones de C1 1 1 1 3 es -12-, de C2 es -12- y de C3 es 0. Determine el ingreso de cada 01 3 país. (a) ⎣⎢⎢ 3 1 0⎦⎥⎥ (b) ⎢⎢⎣ 2 4 ⎥⎥⎦ 1 2 1 3 1 3 2 4 1 − 1 0 0 1 0 2 2 3 ⎡ ⎤⎡ ⎤ 1 − 2 1 1 5 3 1 4 ⎢⎣⎢ 3 2 ⎥⎥⎦ (d) ⎢⎢⎣0 6 ⎥⎥⎦ En los ejercicios del 7 al 10, determine cuáles matrices son pro- 1 (c) 2 2 1 4 1 ducti⎡vas. ⎤ ⎡⎤ 3 3 2 6 0 0⎦⎥⎥ 010 0 1 0 1 1 0 2 0 2 3 3 0⎥⎥⎦ ⎣⎢⎢ 2 ⎢⎣⎢ En los ejercicios 2 a 4, determine un vector p ≥ 0, con al menos 7. 2 8. 1 0 0 3 2 un componente positivo, que satisfaga la ecuación (8) para la 1 02 0 1 0 4 matriz de intercambio dada. ⎡⎤ ⎡⎤ 1 1 1 1 ⎡ ⎤ ⎡⎤ 0 3 0 3 ⎢⎢⎣ 2 ⎦⎥⎥ ⎢⎣⎢ 3 ⎥⎦⎥ 1 2 0 1 1 2 9. 1 0 10. 1 0 3 0 2 1 4 1 2. ⎣⎢⎢ 3 1 ⎥⎦⎥ 3. ⎢⎢⎣ 2 03 ⎥⎦⎥ 4 6 0 4 1 0 1 1 0 1 2 0 3 4 3 3 3 1 13 1 0 1 11. Suponga que la matriz de consumo para el modelo de pro- 3 34 2 3 ducción lineal es ⎡⎤ ⎡⎤ 1 ⎢⎢⎣ 0 3 1 11 0⎥⎥⎦ 4. 1 1 ⎣2 2⎦. 6 6 11 24 5 1 0 6 2 65. Considere la economía simple del ejemplo 1. Suponga que (a) Determine el vector de producción para el vector de seytoul,ma12g13edriedc15leuvdlltaeeoslrhtaiacdlboiomin;tsaequcnumitóeoen,eyl25231cdad21reepdllieaanlltihevmareobesitnctitadoocon,i;sóuy31nmqdyueenelaa25edlhadsaedablesiatltraleicmicóeonnn-- vestido. Determine la matriz de intercambio A para este demanda 1 . problema y un vector p ≥ 0, con al menos un componente 3 positivo, que satisfaga la ecuación (8). (b) Determine el vector de producción para el vector de demanda 2 . 0 66. Considere el modelo de comercio internacional formado por 12. Un pequeño pueblo tiene tres industrias primarias: una mina tres países, C1, C2 y C3. Suponga que la fracción del ingreso de cobre, un ferrocarril y una planta de energía eléctrica. Para producir $1 de cobre, la mina gasta $0.20 de cobre,

166 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) $0.10 de transporte y $0.20 de energía eléctrica. Para pro- ponga que durante el año hay una demanda externa de 1.2 porcionar $1 de transporte, el ferrocarril requiere $0.10 de millones de dólares de cobre, 0.8 millones de dólares de cobre, $0.10 de transporte y $0.40 de energía eléctrica. Para transporte y 1.5 millones de dólares por concepto de energía producir $1 de energía eléctrica, la planta destina $0.20 de eléctrica. ¿Cuánto debe producir cada industria para satisfa- cobre, $0.20 de transporte y $0.30 de energía eléctrica. Su- cer las demandas? Ejercicios teóricos T.1. En el modelo de intercambio (ejemplos 1 o 2), de- muestre que Ap ≤ p implica que Ap = p. 2.7 INTRODUCCIÓN A WAVELETS (ONDELETAS U ONDITAS) Requisito. Lectura de la sección 1.7, La inversa de una matriz. La capacidad de transmitir energía fue uno de los cambios más importantes que se die- ron en el siglo XIX. En el siglo XX ocurrió otra revolución —que continúa hasta nues- tros días— de similar envergadura: la capacidad para transmitir información. Una vez que se tuvo la infraestructura para transmitir datos, la creciente necesidad de informa- ción por parte de los gobiernos y las entidades comerciales exigió que se resolviese có- mo transmitir rápidamente lo esencial del conjunto de datos, de modo que pudiera ser reconstruido para recuperar de manera confiable la información original. Para lograrlo se han desarrollado diversos esquemas que transforman el conjunto de datos original, lo comprimen, lo transmiten y recuperan aproximaciones a la información de origen. Ejemplos de tales esquemas son el código Morse, los codificadores de muchas clases (incluyendo claves públicas de encriptación), las señales de radio, televisión y microon- das, así como los métodos que emplean técnicas privadas de codificación digital. Una técnica de codificación digital muy conocida y disponible comercialmente, es la desarrollada por el Grupo Unido de Expertos en Fotografía (JPEG, por sus siglas en inglés) para imágenes digitales. El esquema JPEG2000 emplea wavelets (ondeletas), una tecnología de compresión que codifica imágenes en una cadena continua. Esta nueva técnica permitirá la creación de archivos de datos 20% más pequeños, la descarga más rápida de información y posibilita seleccionar el tamaño de una imagen sin crear un ar- chivo separado. El tema matemático de las wavelets ha recibido gran atención debido a su versatilidad para adaptarse a una miríada de aplicaciones, incluyendo la compresión de datos para su transmisión eficiente, y la aproximación precisa de información, proce- samiento de imágenes (tal como archivos dactilográficos de la Oficina Federal de Inves- tigación de Estados Unidos, FBI), procesamiento de señales (como restauración de registros), sismología y en la resolución numérica de ecuaciones diferenciales parciales. Así, las wavelets han sido objeto de investigación continua desde la década pasa- da, y su uso continúa adaptándose a un creciente número de áreas científicas y de inge- niería. En esta sección nos proponemos demostrar cómo los conceptos comunes de matri- ces pueden utilizarse para revelar la naturaleza básica de las wavelets. Mostraremos de qué manera la información digital se transforma, permitiendo omitir parte de la misma (proceso conocido como compresión) y luego se transmite para que los datos recibidos puedan reconstruirse como una aproximación certera de la información original. La economía se presenta cuando existe una reducción significativa en la cantidad de infor- mación que se transmite. Por lo tanto, los esquemas de transformación y compresión, junto con el proceso de reconstrucción, deben diseñarse con esta clase de economía en mente. En la figura 2.22 se representa gráficamente este escenario.

Sec. 2.7 Introducción a wavelets (ondeletas u onditas) 167 Figura 2.22 ᭤ Transformación Datos originales Compresión Información Transmisión aproximada EJEMPLO 1 En cada una de las columnas de la tabla 2.2 se muestra una representación de un dólar- como combinación de las monedas indicadas. La entrada en un fila indica el número de monedas del tipo correspondiente a dicha fila. Los detalles de la información acerca de cualquiera de estas cinco maneras de representar un dólar podrían transmitirse en- viando la cadena de seis números correspondiente a una columna. Sin embargo, varias de estas representaciones pueden comprimirse de modo que se envían menos de seis nú- meros, pero la información transmitida permite reconstruir de manera exacta la infor- mación original. La información de la primera columna, [0 0 4 0 0 0]T, se puede comprimir a [4 3]T, lo cual significaría cuatro monedas del tercer tipo (mone- das de $0.25). De manera análoga, la segunda columna, [0 0 2 5 0 0] T, puede comprimirse a [2 5 3 4]T, lo cual significaría dos monedas de $0.25 y cinco de $0.10. (Observe que las primeras dos entradas proporcionan el número de monedas, y las segundas dos entradas la posición en la lista de los tipos de monedas.) Aunque no todas las columnas de la tabla 2.2 pueden comprimirse de manera tan sencilla, en el caso de conjuntos grandes de datos en los que aparece una gran cantidad de ceros (tales datos se denominan esparcidos, dispersos o poco densos), una compresión puede ser tan sencilla como enviar un dígito distinto de cero y su posición en la cadena de información. ■ Tabla 2.2 Moneda de un dólar 0 0 0 0 0 $0.50 00 1 0 1 $0.25 42 1 0 1 $0.10 05 1 0 1 $0.05 00 0 1 1 $0.01 0 0 15 95 10 Otro ámbito en donde la compresión de información resulta útil, es en el de las imágenes, ya que suele implicar la transmisión de grandes cantidades de datos. Los avances continuos en calculadoras y computadoras han puesto a disposición del usua- rio sencillos dispositivos para mostrar funciones matemáticas a través de gráficas. Cuando la función f se grafica, por medio de un procedimiento común se genera un con- junto de valores de x igualmente espaciados, y se calcula el valor de la función en cada uno de tales valores. Luego se despliega la gráfica de f mostrando los puntos (x, f (x)) conectados por segmentos de recta, o quizá por arcos, para presentar una curva suave. Si el espaciado entre los valores de x es grande, la gráfica tal vez se vería dentada, en lugar de mostrar un trazo suave. En el caso de imágenes de alta calidad, podría necesi- tarse un espaciado muy pequeño, por lo que el conjunto de datos originales {(x, f (x))} tendría que ser muy grande. Las imágenes gráficas y las fotografías digitales están for- madas de cientos o miles de pequeños puntos. Una descripción matemática de tal imagen proporciona la posición de cada punto y un código que denota un color o la escala de grises que corresponde al punto. El conjunto de datos resultante es muy grande, inclu- so tratándose de imágenes pequeñas.

168 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) La transmisión de las grandes cantidades de datos necesarias para la representación de imágenes es una preocupación real, y puede causar retraso en una red de compu- tadoras. Para evitar dificultades de este tipo, una posible solución es el uso de esque- mas de “transformación + compresión” que reducen la cantidad de datos que se necesita transmitir, junto con métodos que utilizan los datos transmitidos para construir buenas aproximaciones a la imagen original. Por transformación damos a entender al- gún proceso que toma los datos digitales originales, o brutos, y produce un conjunto de información equivalente utilizando, muchas veces, algún tratamiento algebraico. Ideal- mente, los datos transformados deben reflejar las cualidades intrínsecas de la informa- ción contenida en ellos. Por compresión nos referimos a un esquema que reduce la cantidad general de datos que se necesita transmitir, de modo que pueda reconstruirse una buena aproximación de la imagen original. A veces los pasos de la transformación y la compresión se realizan de forma simultánea. Los procesos de transformación y compresión se ilustran por medio de la gráfica de una función f evaluada en puntos igualmente espaciados. En el caso de una cadena o vector de datos de coordenadas y de un conjunto de puntos en la gráfica de la función f, desarrollamos un conjunto equivalente de datos usando las operaciones de prome- diar y diferenciar; éste es el paso de transformación. El conjunto equivalente de datos que resulta contiene toda la información del conjunto original. Una característica de esta forma equivalente del conjunto de datos es que puede comprimirse con mayor facilidad;* éste es el paso de compresión. El conjunto de datos comprimidos pierde parte de la información original, pero en muchos casos se puede reconstruir una buena aproximación a partir de este conjunto más pequeño de datos; éstos son los pasos de transmisión y reconstrucción. A continuación demostraremos cómo utilizar la multipli- cación de matrices para realizar el paso de transformación, y cómo utilizar las propie- dades algebraicas para verificar que obtenemos un conjunto equivalente de datos. EJEMPLO 2 (Cálculo de promedios por medio de multiplicación matricial) (a) Para el vector a calculamos el promedio de las entradas usando el siguiente pro- b ducto de fila por columna 11 a = a+b . 22 b 2 (b) A continuación se desarrolla el caso para cuatro valores, en donde queremos pro- mediar pares sucesivos de valores (acción denominada promedio por pares). Pa- ra los datos iniciales ⎡a⎤ v = ⎢⎣bc⎥⎦ d necesitamos que el resultado de la multiplicación de matrices sea ⎡⎤ ⎢⎢⎣⎢ a + b ⎥⎥⎥⎦ . c 2 d + 2 *Un esquema de compresión sencillo consiste en eliminar un dato sí y otro no, pero existen técnicas que pier- den menos información aprovechando la ventaja de regiones en las que una función no cambia demasiado. El uso de promediar y diferenciar ofrece ese beneficio.

Sec. 2.7 Introducción a wavelets (ondeletas u onditas) 169 Una matriz A por el vector v, de 4 × 1, produce un vector 2 × 1, por lo que la ma- triz A debe ser de 2 × 4. Usando el resultado del inciso (a), resulta que ⎡⎤ ⎡ ⎤ a 1 1 0 0 ⎢⎢⎢⎣bc⎥⎥⎦⎥ = ⎢⎣⎢⎢ a + b ⎥⎦⎥⎥ 2 2 c 2 d 1 1 + 0 0 2 2 d2 proporciona el promedio por pares. En consecuencia, la matriz que realiza la trans- formación a promedios por pares es A= 1 1 0 0 2 2 1. 1 0 0 2 2 (c) En el caso de seis valores en un vector v, se utiliza la matriz A, de 3 × 6 —que se muestra a continuación— en el producto Av para calcular el promedio por pares de las entradas en v. ⎡⎤ 1 1 0 0 0 0 2 0 0⎥⎦ . A = ⎢⎣ 2 1 1 0 2 2 0 0 0 0 0 1 1 2 2 (Verifique que si v = [a b c d e f ]T, entonces Av proporciona un vector, de 3 × 1, que contiene los promedios por pares de las entradas de v.) ■ Nuestra transformación de datos debe ser tal que podamos recuperar los datos ori- ginales a partir de la forma alternativa equivalente que obtuvimos. Para garantizar la po- sibilidad de una recuperación exacta, desarrollamos una representación equivalente de la información en el vector original, formando una pareja con otra parte de la informa- ción y con un promedio. Para desarrollar lo anterior procedemos como sigue. Partimos de la premisa de que el vector v = a puede reemplazarse por el vector w = c , donde c = a+b b d 2 es el promedio de las entradas en v, y d = a − c es la distancia entre la primera entra- da de v y el promedio. Esto se obtiene a partir de la observación de que, si conocemos los valores de c y d, entonces a = c + d y b = 2c − a, así que hemos obtenido los valores de a y b. A continuación nos interesa lograr una formulación matricial de la transformación de datos, de a c ⎡a + b⎤ b d v= a w= = ⎣ 2 ⎦. a−c Por lo tanto, buscamos una matriz de 2 × 2 A tal que A a = c = c . b d a−c Con base en el trabajo anterior, resulta que la primera fila de la matriz A debe ser 1 1 para que c sea el promedio de a y b. Denotemos la segunda fila de A mediante 2 2

170 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) [p q], y determinemos estos valores. A partir de la multiplicación matricial, se obtiene p q a = a − c. b Realizando la multiplicación del lado izquierdo, obtenemos pa + qb = a − c. Al sus- tituir b por la expresión equivalente, 2c − a, y agrupar términos, tenemos pa + q(2c − a) = ( p − q)a + (2q)c = a − c. Igualando los coeficientes de términos semejantes, se obtiene el sistema lineal p−q= 1 2q = −1, cuya solución es p = 1 , q =− 1 . En consecuencia, la formulación matricial para 2 2 calcular el promedio y la distancia entre la primera entrada y el promedio es ⎡⎤ 1 1 a c promedio de a y b b a−c distancia entre a y el promedio ⎣2 2⎦ = = , 1 1 − 2 2 o si ⎡ ⎤ 1 1 a c Q = ⎣2 2⎦, v= b y w= a−c 1 1 − 2 2 tenemos Qv = w. A este procedimiento le llamamos formulación matricial de la re- presentación promedio-diferencia. Observe que la matriz Q es no singular, y que Q−1 = 1 1 (verifique). 1 −1 Por lo tanto, si conocemos el promedio de los dos valores y la distancia entre el prime- ro y el promedio, podemos recuperar los datos originales; esto es, v = Q−1w = 1 1 c = a . 1 −1 a−c b (Esto se mostró anteriormente por medio de álgebra básica.) EJEMPLO 3 Ampliaremos la representación promedio-diferencia a un vector con más de dos entra- das, a fin de determinar los promedios por pares y las correspondientes diferencias. (a) Sea v = [a b c d]T. Ahora determinamos una matriz A, de 4 × 4, tal que ⎡promedio de a y b ⎤ Av = ⎢⎣pdrisotmanecdiiaoednetrce y d el promedio⎥⎦ . a y distancia entre c y el promedio Usando el ejemplo 2 y repitiendo el desarrollo anterior para el caso de dos datos, una conjetura plausible para la matriz A es ⎡1 1 00 ⎤ ⎢⎣⎢⎢ 2 2 1 012 ⎥⎥⎦⎥ . 2 0 0 0 1 − 1 2 2 1 1 00 2 − 2

Sec. 2.7 Introducción a wavelets (ondeletas u onditas) 171 Verifique que esta conjetura es correcta y que A es no singular; además, determine A−1. (b) Para un 6-vector v = [a b c d e f ]T, formule una conjetura para una ma- triz de 6 × 6 tal que ⎡promedio del primer par de datos ⎤ Av = ⎢⎣⎢⎢⎢⎢dppdriirssoottmmaanneeccddiiiiaaooeeddnneettlrrleetseeacrgcyyueneredllpopparrrpoodammreeeddddeaiitoodoastos⎦⎥⎥⎥⎥⎥ . distancia entre e y el promedio Verifique su conjetura y compruebe que la matriz A es no singular. ■ A continuación, presentamos un resumen de nuestros desarrollos hasta el momen- to. Dado un vector v de valores de una función en puntos igualmente espaciados, he- mos encontrado cómo determinar una matriz A de modo que Av sea un vector que contenga los promedios por pares, seguidos de las distancia entre el primer elemento de cada par y el promedio. El siguiente paso de nuestra transformación consiste en aplicar el mismo concepto a estos promedios de modo que, en efecto, calculemos promedios de promedios y las distancias entre éstos y los promedios originales. Sin embargo, de- bemos asegurar la conservación de las distancias entre el primer elemento de cada par de datos y sus promedios. Para ilustrar que no hay que realizar nuevo trabajo técnico, sino únicamente una reorganización de los resultados que ya hemos determinado, consi- deremos el caso de cuatro valores de una función, designados por v = [a b c d ]T. Sea A1 la matriz que transforma estos datos a los promedios y diferencias analizadas en el inciso (a) del ejemplo 2. Tenemos ⎡ 1 1 ⎤ 2 A1v = ⎢⎣⎢⎢⎢⎢ 2 0 0 ⎡a⎤ = ⎡ e ⎤ , 0 012 ⎥⎥⎥⎥⎥⎦ ⎢⎣bc⎥⎦ f ⎥⎦ 0 1 ⎣⎢ a − − 1 2 d c − e 1 2 f 2 0 0 0 1 − 1 2 2 donde e = a + b y f = c + d . 2 2 ⎡e⎤ Sea w = ⎣⎢ a f e ⎥⎦. Ahora queremos determinar una matriz de 4 × 4, A2, tal que − c− f ⎡g⎤ u = A2w = ⎢⎣ e − g ⎥⎦ , donde g = e+ f . a − e 2 c− f (Observe que e − g es la distancia entre e y el promedio de e y f.) Como podemos ver, las últimas dos entradas del vector w y del vector ⎡g⎤ u = ⎢⎣ e − g ⎦⎥ a − e c− f son iguales, lo que nos permite sospechar que una parte de la matriz A2 será una iden- tidad. Además, como A2 sólo transforma las primeras dos entradas de w, habrá ceros.

172 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) Conjeturamos que A2 será una matriz por bloques que tendrá la forma A2 = Q O2 , O2 I2 donde O2 es una matriz de ceros de 2 × 2, I2 es una matriz identidad de 2 × 2, y Q es una matriz de 2 × 2 que debe determinarse. Inspeccionando el producto matricial ⎡e⎤ ⎡g⎤ u = A2w = Q O2 ⎣⎢ a f e ⎥⎦ = ⎣⎢ ea − g ⎥⎦ , O2 I2 − − e c− f c− f encontramos que Q debe elegirse de modo que Q e = g . f e−g Pero esto es lo mismo que producir un promedio y la distancia entre la primera entra- da y el promedio. Con base en el trabajo anterior, resulta que ⎡⎤ 1 1 Q = ⎣2 2⎦, − 1 1 2 2 y, por lo tanto, ⎡⎤ 1 1 0 000⎦⎥⎥⎥⎥⎥ . 2 0 ⎣⎢⎢⎢⎢⎢ 2 1 A2 = 1 − 1 2 2 0 0 0 001 Tenemos la siguiente sucesión de transformaciones de datos: ⎡a⎤ ⎡e⎤ ⎡g⎤ v = ⎣⎢bc⎥⎦ → A1v = ⎢⎣ a f e ⎦⎥ = w → u = A2w = ⎣⎢ ea − g ⎥⎦ . − − e d c− f c− f El anterior conjunto de pasos es equivalente al producto u = A2A1v. En el vector ⎡e⎤ w = ⎣⎢ a f e ⎦⎥ , − c− f las entradas e y f se denominan promedios, y a − e y c − f son los coeficientes de detalle. De manera análoga, en el vector ⎡g⎤ u = ⎣⎢ e − g ⎥⎦ a − e c− f la entrada g es el promedio final, y las últimas tres entradas son los coeficientes de de- talle. La información intrínseca del conjunto original de datos se ha transformado en los coeficientes de detalle y el promedio final. Puede demostrarse que las matrices A1 y A2

Sec. 2.7 Introducción a wavelets (ondeletas u onditas) 173 son no singulares (vea el ejercicio 6), por lo que el proceso se puede invertir; esto es, hemos generado una representación equivalente a los datos originales. En el caso de más de cuatro valores, cabe esperar que crecerá el tamaño de las ma- trices necesarias para realizar la transformación de los datos originales a un promedio final y coeficientes de detalle. Como estamos calculando promedios de pares de ele- mentos, se deduce que siempre debemos tener un número par de elementos en cada ni- vel de los promedios. De aquí que, idealmente, deberíamos utilizar este procedimiento sobre conjuntos con 2, 4, 8, 16, . . . , 2 n elementos. En caso de que el tamaño de nues- tro vector de datos no sea una potencia de 2, podemos adjuntar ceros al final del vector para que cumpla con el requisito, para luego proceder a la transformación de los datos como se describió anteriormente. EJEMPLO 4 Sea v = [37 33 6 16]T una muestra de una función f en cuatro puntos igualmente espaciados. Para determinar el promedio y los coeficientes de detalle, transformamos los datos usando las matrices A1 y A2, dadas previamente, como sigue: ⎡⎤⎡⎤ (Verifique.) 35 23 w = A2 A1v = A2( A1v) = A2 ⎢⎢⎣⎢ 112⎦⎥⎥⎥ = ⎢⎢⎣⎢ 122⎥⎥⎥⎦ . −5 −5 Así, el promedio final es 23 y los coeficientes de detalle son 12, 2 y −5. Observe que ambas matrices, A1 y A2, pueden escribirse como matrices por bloques. Sea P = P1 P2 = 11 00 22 11 00 22 y S = S1 S2 = 1 − 1 00 . 2 2 1 1 00 2 − 2 Entonces, A1 = P1 P2 S1 S2 y, de acuerdo con lo anterior, ⎡ ⎤ Q O2 , 1 1 O2 I2 A2 = donde Q = ⎣ 2 2 ⎦. − 1 1 2 2 Como se muestra en el ejemplo 5, generalizar esta forma por bloques para las matrices que se utilizan en la transformación resulta sencillo. ■ Una vez que tenemos el promedio final y los coeficientes de detalle, hemos com- pletado la transformación de los datos a la representación equivalente de promedio-di- ferencia. Recuerde que en esta etapa podemos recuperar todos los datos originales. A continuación realizaremos una compresión. Una forma sencilla de llevarla a cabo con- siste en hacer igual a cero un coeficiente de detalle si su valor absoluto es menor que un número de umbral, e, preestablecido. Reemplazar un coeficiente de detalle peque- ño por cero tiene el mismo efecto que reemplazar un dato por un promedio de valores de datos. En consecuencia, si la función no cambia con rapidez en esa región, obtenemos

174 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) una buena aproximación. (En general, la elección de un número de umbral depende de la aplicación, y suele basarse en la experimentación con aplicaciones similares.) Una vez que determinemos el conjunto de datos comprimidos, sólo necesitamos transmitir los coeficientes distintos de cero y sus posiciones (esto es, para nuestros ejemplos, el índice de sus columnas). Cuando el conjunto de datos es grande, puede ha- ber una extraordinaria reducción en la cantidad de datos que deben transmitirse. Al re- cibir los datos comprimidos revertimos las transformaciones de diferenciar y promediar para generar una aproximación al conjunto de datos originales. El proceso inverso uti- liza las inversas de las matrices A1, A2, . . . , An, así que no se requieren conceptos adi- cionales en esta etapa; sólo formamos los productos matriciales por medio de las inversas de las matrices que se utilizaron en la transformación. Las inversas que se uti- lizan no son difíciles de calcular, toda vez que contamos para ello con sencillos patro- nes por bloques. De acuerdo con el ejemplo 4, tenemos ⎡ 11 ⎤−1 ⎡ ⎤ A1−1 = ⎣⎢⎢⎢⎢⎢ 22 0 0 ⎥⎥⎥⎦⎥⎥ = ⎢⎣⎢⎢⎢ 1 0 1 0 ⎦⎥⎥⎥⎥ 1 0 −1 0 00 1 1 2 2 0 1 0 1 1 − 1 1 2 2 0 0 0 −1 00 1 − 1 0 2 2 ⎡1 0 1 0⎤ = ⎢⎣01 0 −1 10⎥⎦ 10 0 1 0 −1 y ⎡⎡ ⎤ ⎤−1 ⎡ ⎤ ⎢⎢⎢⎢⎢⎢⎣⎣ 11 0 0 ⎦⎥⎥⎥⎥⎥⎥ 0 0 2 2⎦ = ⎢⎢⎣⎢⎢ 1 1 0 0 ⎥⎥⎥⎥⎦ 1 1 0 1 −1 0 0 A−2 1 = 2 − 1 2 0 0 1 0 0 0 00 01 00 01 ⎡1 1 0 0⎤ = ⎢⎣01 −1 0 00⎥⎦ . 0 1 00 01 Si w˜ es la información comprimida, la aproximación a los datos originales está dada por y˜ = A−1 1 A2−1w˜ . EJEMPLO 5 Suponga que tenemos la siguiente muestra de valores x y y a partir de la gráfica de una función. x 1 23 4 5 6 78 y 37 33 6 16 26 28 18 4 Si v es el vector de 8 × 1 de coordenadas de y, sean P = P1 P2 y S = S1 S2 ,

Sec. 2.7 Introducción a wavelets (ondeletas u onditas) 175 como en el ejemplo 4, y definimos Z= 0 0 e I= 1 0 . 0 0 0 1 Sea A1 la matriz de 8 × 8 por bloques dada por ⎡ P1 P2 Z ⎤ Z A1 = ⎢⎢⎣⎢ Z Z P1 PZ2⎥⎥⎦⎥ . S1 S2 Z S2 Z Z S1 Entonces tenemos (verifique) A1v = 35 11 27 11 2 −5 −1 7 T , donde las primeras cuatro entradas son promedios (por pares) y las últimas cuatro en- tradas son los coeficientes de detalle (de primer nivel). Ahora construimos la matriz por bloques A2 de 8 × 8, de esta manera ⎡⎤ P1 P2 Z Z ⎣⎢⎢⎢ ⎦⎥⎥⎥ A2 = S1 S2 Z Z . Z Z I Z Z ZZ I De lo anterior resulta (verifique) que A2( A1v) = 23 19 12 8 2 −5 −1 7 T . En este resultado, las primeras dos entradas son promedios y las últimas seis son coe- ficientes de detalles (de segundo nivel). Por último, construimos la matriz por bloques A3 de 8 × 8, de este modo ⎡⎤ ⎣⎢⎢⎢ QZZZ ⎥⎥⎥⎦ A3 = Z I Z Z , Z Z I Z ZZZ I donde ⎡ ⎤ 1 1 Q = ⎣2 2⎦ 1 1 − 2 2 como se desarrolló anteriormente. De ello resulta (verifique) que A3[ A2( A1v)] = w = 21 2 12 8 2 −5 −1 7 T , donde la primera entrada es el promedio (final) de los ocho datos originales, y las res- tantes siete entradas son los coeficientes de detalle (de tercer nivel). Para comprimir los datos en este ejemplo, igualamos a cero los coeficiente de detalles cuyo valor absoluto sea menor o igual a 3; esto es, utilizamos un número de umbral e = 3. La información comprimida resultante es el vector de 8 × 1 w˜ = 21 0 12 8 0 −5 0 7 T . Sólo necesitamos transmitir las entradas distintas de cero de este vector y sus posi- ciones.

176 Capítulo 2 Aplicaciones de ecuaciones lineales y matrices (opcional) Al recibir el vector w˜ , podemos construir un modelo que aproxime la información original calculando y˜ = ( A1)−1( A2)−1( A3)−1w˜ = 33 33 4 14 29 29 20 6 T . Para comparar visualmente los datos originales con el modelo desarrollado como un re- sultado del esquema de transformación/compresión, trazamos el conjunto de datos ori- ginales y el conjunto de datos que lo aproximan. Vea la figura 2.23. x 1 23 4 5 6 78 y˜ 33 33 4 14 29 29 20 6 Figura 2.23 ᭤ 40 30 20 10 0 02468 Los puntos designados por los signos + indican un modelo que aproxima los da- tos originales, denotados por el símbolo o. Este modelo se denomina wavelet y, consi- derando que en su elaboración intervienen muy pocos datos, es una aproximación sor- prendentemente buena. ■ Para descubrir el potencial completo de las wavelets debemos utilizar grandes con- juntos de datos. Para un conjunto inicial de 512 = 29 datos, nueve aplicaciones de nues- tra técnica de promediar y diferenciar producen un resultado de un promedio (final) y 511 coeficientes de detalle. A partir de ello podemos aplicar nuestra estrategia de com- presión, esto es, elegir un número de umbral que se utiliza para introducir ceros de mo- do que nos permita transmitir menos datos y sus posiciones. Al invertir los pasos de diferenciar y promediar, obtenemos una wavelet que con frecuencias es una muy bue- na aproximación a la información original. Las figuras 2.24(a)-(c) muestran aproximaciones wavelet para muestras discretas de f (x) = e x cos(/ x) en el intervalo [0, 3]. Los datos se eligieron en n puntos igualmen- te espaciados, y se utilizó un número de umbral e en la compresión. Los puntos indica- dos con el símbolo o representan los datos muestrales originales, y los señalados con el símbolo + representan los datos de la wavelet. Nuestro análisis sobre wavelets se ha limitado a conjuntos de datos discretos igual- mente espaciados, es decir, pares ordenados. Hemos ilustrado la sucesión de operacio- nes, esto es, la transformación de los datos a una representación equivalente que puede invertirse para obtener la información original, la compresión de los datos por medio de un número de umbral que convierte en cero aquellos valores que están por abajo de un número de umbral seleccionado, y la construcción de una aproximación a los datos originales, es decir, una wavelet. La transmisión de los datos comprimidos presenta un ahorro de tiempo significati- vo, en comparación con la transmisión de los datos originales. Además, el espacio re- querido para almacenar los datos comprimidos puede ser significativamente menor que