Multiplicación de matrices

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de agosto de 2022; las comprobaciones requieren 2 ediciones .

La multiplicación de matrices es una de las operaciones básicas sobre matrices . La matriz resultante de la operación de multiplicación se llama producto de matrices . Los elementos de la nueva matriz se obtienen a partir de los elementos de las antiguas matrices según las reglas ilustradas a continuación .

Las matrices y se pueden multiplicar si son compatibles en el sentido de que el número de columnas de la matriz es igual al número de filas . $A$ $B$ $A$ $B$

Las matrices tienen muchas de las propiedades de multiplicación algebraica que tienen los números ordinarios, con la excepción de la conmutatividad .

Para matrices cuadradas, además de la multiplicación, se puede introducir la operación de elevar una matriz a una potencia y la matriz inversa .

Mientras que las matrices se utilizan para describir, en particular, transformaciones de espacios matemáticos ( rotación , reflexión , estiramiento y otros), el producto de matrices describirá la composición de las transformaciones .

Definición

Sean dos matrices rectangulares y de dimensiones y dadas, respectivamente: $A$ $B$ ${\ estilo de visualización l \ veces m}$ $m\veces n$

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1m}\\a_{21}&a_{22}&\cdots &a_{2m}\\\vdots &\vdots &\ddots &\vdots \\a_{l1}&a_{l2}&\cdots &a_{lm}\end{bmatrix}},\;\;\;B={\begin{bmatrix}b_{11}&b_{ 12}&\cdots &b_{1n}\\b_{21}&b_{22}&\cdots &b_{2n}\\\vdots &\vdots &\ddots &\vdots \\b_{m1}&b_{m2}& \cdots &b_{mn}\end{bmatriz}}.

Entonces la matriz con dimensiones : $C$ ${\ estilo de visualización l \ veces n}$

C={\begin{bmatrix}c_{11}&c_{12}&\cdots &c_{1n}\\c_{21}&c_{22}&\cdots &c_{2n}\\\vdots &\vdots &\ddots &\vdots \\c_{l1}&c_{l2}&\cdots &c_{ln}\end{bmatriz}},

donde:

c_{ij}=\sum _{r=1}^{m}a_{ir}b_{rj}\;\;\;\left(i=1,2,\ldots l;\;j =1,2,\ldots n\right).

se llama su producto .

La operación de multiplicar dos matrices es factible solo si el número de columnas del primer factor es igual al número de filas del segundo; en este caso se dice que las matrices son consistentes . En particular, la multiplicación siempre es factible si ambos factores son matrices cuadradas del mismo orden.

Así, la existencia de una obra no sigue en absoluto a la existencia de una obra. $AB$ $LICENCIADO EN LETRAS.$

Ilustración

El producto de matriz AB consta de todas las combinaciones posibles de los productos internos de los vectores de fila de la matriz A y los vectores de columna de la matriz B. El elemento de la matriz AB con índices i, j es el producto escalar del i -ésimo vector fila de la matriz A y el j -ésimo vector columna de la matriz B.

La ilustración de la derecha muestra el cálculo del producto de dos matrices A y B , muestra cómo cada intersección en el producto de matrices corresponde a las filas de la matriz A y las columnas de la matriz B. El tamaño de la matriz resultante es siempre el máximo posible, es decir, para cada fila de la matriz A y columna de la matriz B siempre hay una intersección correspondiente en el producto de la matriz.

Los valores en las intersecciones marcadas con círculos serán:

${\begin{alineado}{\color {Rojo}x_{1,2}}&=(a_{1,1},a_{1,2})\cdot (b_{1,2},b_{2, 2})\\&=a_{1,1}b_{1,2}+a_{1,2}b_{2,2}\\{\color {Azul}x_{3,3}}&=( a_{3,1},a_{3,2})\cdot (b_{1,3},b_{2,3})\\&=a_{3,1}b_{1,3}+a_{ 3,2}b_{2,3}\end{alineado}}$

En general, el producto de matrices no es una operación conmutativa. Por ejemplo:

{\overset {3\times 4{\text{matriz))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\color {Azul}1&\color {Azul}2&\color {Azul}3&\color {Azul}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrix}}}{\begin {bmatrix}\cdot &\cdot &\cdot &\color {Red}a&\cdot \\\cdot &\cdot &\cdot &\color {Red}b&\cdot \\\cdot &\cdot &\cdot & \color {Red}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{ matriz ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatriz}}}

El elemento del producto de las matrices anteriores se calcula de la siguiente manera $x_{{3,4}}$

x_{3,4}=({\color {Azul}1},{\color {Azul}2},{\color {Azul}3},{\color {Azul}4})\cdot ({\color {Rojo}a},{\color {Rojo}b},{\color {Rojo}c},{\color {Rojo}d})={\color {Azul}1}\cdot {\color {Rojo} a}+{\color {Azul}2}\cdot {\color {Rojo}b}+{\color {Azul}3}\cdot {\color {Rojo}c}+{\color {Azul}4}\ cdot {\ color {Rojo} d}

La primera coordenada en la designación de matriz denota una fila, la segunda coordenada denota una columna; este orden se utiliza tanto para la indexación como para el dimensionamiento. El elemento en la intersección de la fila y la columna de la matriz resultante es el producto escalar de la i-ésima fila de la primera matriz y la i-ésima columna de la segunda matriz. Esto explica por qué el ancho y el alto de las matrices multiplicadas deben coincidir: de lo contrario, el producto escalar no está definido. $x_{{\color {Azul}i}{\color {Rojo}j))$ $i$ $j$ $i$ $j$

Discusión

Es más fácil ver las razones de la regla descrita de la multiplicación de matrices considerando la multiplicación de un vector por una matriz.

Este último se introduce naturalmente en base al hecho de que al descomponer vectores en términos de una base , la acción de (cualquier) operador lineal A da la expresión para los componentes del vector v' = A v :

v'_{i}=\sum \limits _{j}A_{ij}v_{j}

Es decir, un operador lineal se representa mediante una matriz, los vectores mediante vectores columna y la acción de un operador sobre un vector mediante la multiplicación de matrices del vector columna de la izquierda por la matriz del operador (este es un caso especial de multiplicación de matrices, cuando una de las matrices, el vector columna, tiene tamaño ). ${\ estilo de visualización n \ veces 1}$

(Igualmente, la transición a cualquier nueva base al cambiar las coordenadas se representa con una expresión completamente similar, solo que en este caso ya no son las componentes del nuevo vector en la base anterior, sino las componentes del vector anterior en la nueva base ; en este caso , los elementos de la matriz de transición a la nueva base). $v'_{i}$ $A_{{ij}}$

Habiendo considerado la acción secuencial sobre el vector de dos operadores: primero A , y luego B (o la transformación de la base A , y luego la transformación de la base B ), aplicando dos veces nuestra fórmula, obtenemos:

v''_{i}=\sum \limits _{j}B_{ij}\sum \limits _{k}A_{jk}v_{k}=\sum \limits _{j}\sum \limits _ {k}B_{ij}A_{jk}v_{k}=\sum \limits _{k}\sum \limits _{j}(B_{ij}A_{jk})v_{k},

de donde se puede ver que la composición BA de la acción de los operadores lineales A y B (o una composición similar de transformaciones de base) corresponde a una matriz calculada por la regla del producto de las matrices correspondientes:

(BA)_{ik}=\sum \limits _{j}B_{ij}A_{jk}.

El producto de matrices definido de esta manera resulta bastante natural y obviamente útil (proporciona una forma simple y universal de calcular composiciones de un número arbitrario de transformaciones lineales).

Propiedades

Propiedad asociativa , asociatividad :

\mathbf {A} (\mathbf {BC} )=(\mathbf {AB} )\mathbf {C} ;

\alpha (\mathbf {AB} )=(\alpha \mathbf {A} )\mathbf {B} =\mathbf {A} (\alpha \mathbf {B} ).

Propiedad distributiva , distributividad con respecto a la suma :

\mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ;

(\mathbf {A} +\mathbf {B} )\mathbf {C} =\mathbf {AC} +\mathbf {BC} .

El producto de una matriz y la matriz identidad de un orden adecuado es igual a la propia matriz: $\mathbf {E}$

\mathbf{EA} =\mathbf{A};

\mathbf{AE} =\mathbf{A}.

El producto de una matriz y una matriz cero de dimensión adecuada es igual a la matriz cero: $\mathbf {0}$

\mathbf{0A} =\mathbf{0};

\mathbf{A0} =\mathbf{0}.

Si y son matrices cuadradas del mismo orden, entonces el producto de matrices tiene otras propiedades. $\matemáticas {A}$ $\matemáticas {B}$

La multiplicación de matrices es en general no conmutativa :

\mathbf {AB} \neq \mathbf {BA} .

Si , entonces se dice que las matrices y conmutan entre sí. $\mathbf{AB} =\mathbf{BA}$ $\matemáticas {A}$ $\matemáticas {B}$

Los ejemplos más simples de matrices de conmutación:

cualquier matriz cuadrada - consigo misma: (cuadrando la matriz); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
cualquier matriz cuadrada — con la matriz identidad del mismo orden: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
cualquier matriz cuadrada — con una matriz cero del mismo orden: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
cualquier matriz cuadrada no singular — con su matriz inversa: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

El determinante y la traza del producto no dependen del orden de multiplicación de matrices:

\det(\mathbf {AB} )=\det(\mathbf {BA} )=\det \mathbf {A} \cdot \det \mathbf {B} ;

{\mbox{tr}}(\mathbf {AB} )={\mbox{tr}}(\mathbf {BA} ).

Matriz inversa

Una matriz cuadrada se llama no singular ( non- singular ) si tiene una única matriz inversa tal que se cumple la siguiente condición: $A$ $A^{{-1}}$

AA^{-1}=A^{-1}A=E.

De lo contrario, la matriz se llama especial ( degenerada ) . $A$

Una matriz de orden es no degenerada si y solo si en este caso existe una matriz cuadrada del mismo orden $A=\izquierda[a_{ik}\derecha]$ $norte$ $\det A=\det \left[a_{ik}\right]\neq 0;$ $A^{{-1}}$ $norte:$

A^{-1}=\left[a_{ik}\right]^{-1}=\left[{\frac {A_{ki}}{\det A}}\right],

donde es el complemento algebraico del elemento en el determinante $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Algoritmos rápidos de multiplicación de matrices

La complejidad de calcular el producto de matrices por definición es , pero existen algoritmos más eficientes [1] que se utilizan para matrices grandes. La cuestión de la velocidad límite de multiplicación de matrices grandes, así como la cuestión de construir los algoritmos prácticos más rápidos y estables para la multiplicación de matrices grandes, sigue siendo uno de los problemas sin resolver del álgebra lineal . $\O(n^{3})$

Algoritmo de Strassen (1969)

El primer algoritmo para la multiplicación rápida de matrices grandes fue desarrollado por Volker Strassen [2] en 1969. El algoritmo se basa en una partición recursiva de matrices en bloques de 2X2 . Strassen demostró que las matrices 2X2 se pueden multiplicar de forma no conmutativa por siete multiplicaciones, por lo que se realizan siete multiplicaciones en cada paso de la recursividad en lugar de ocho. Como resultado, la complejidad asintótica de este algoritmo es . La desventaja de este método es la mayor complejidad de programación en comparación con el algoritmo estándar, poca estabilidad numérica y una mayor cantidad de memoria utilizada. Se han desarrollado una serie de algoritmos basados en el método de Strassen, que mejoran la estabilidad numérica, la tasa constante y otras características. Sin embargo, debido a su simplicidad, el algoritmo de Strassen sigue siendo uno de los algoritmos prácticos para multiplicar matrices grandes. Strassen también planteó la siguiente conjetura de Strassen : para arbitrariamente pequeño , existe un algoritmo que, para números naturales n suficientemente grandes, garantiza la multiplicación de dos matrices de tamaño en operaciones.

O(n^{\log _{2}7})\aprox. O(n^{2.81})

\varepsilon >0

n\veces n

O(n^{2+\varepsilon})

Mejoras adicionales al exponente ω para la velocidad de multiplicación de matrices

En el futuro, las estimaciones de la tasa de multiplicación de matrices grandes se mejoraron muchas veces. Sin embargo, estos algoritmos eran teóricos, en su mayoría aproximados. Debido a la inestabilidad de los algoritmos de multiplicación aproximada, actualmente no se utilizan en la práctica.

Algoritmo de Pan (1978)

En 1978 Pan [3] propuso su propio método de multiplicación de matrices, cuya complejidad era Θ(n 2.78041 ) .

Algoritmo de Beanie (1979)

En 1979, un grupo de científicos italianos liderados por Bini [4] desarrollaron un algoritmo para la multiplicación de matrices usando tensores. Su complejidad es Θ(n 2.7799 ) .

Algoritmos de Schönhage (1981)

En 1981, Schönhage [5] introdujo un método que funciona a una tasa de Θ(n 2.695 ) . La estimación se obtiene usando un enfoque llamado multiplicación de matriz parcial . Posteriormente, logró obtener la estimación Θ(n 2.6087 ) . Luego, Schönhage obtuvo la estimación de complejidad Θ(n 2.548 ) con base en el método de las sumas directas . Romani pudo degradar a Θ(n 2.5166 ) , mientras que Pan pudo degradar a Θ(n 2.5161 ) .

Algoritmo de Coppersmith-Winograd (1990)

En 1990, Coppersmith y Winograd [6] publicaron un algoritmo que, modificado por Williams Wasilewska [7] en 2011, multiplica matrices a razón de O(n 2,3727 ) . Este algoritmo utiliza ideas similares al algoritmo de Strassen. Hasta la fecha, las modificaciones del algoritmo de Coppersmith-Winograd son las más asintóticamente rápidas. Pero el hecho de que las mejoras obtenidas sean despreciables permite hablar de la existencia de la "barrera de Coppersmith-Winograd" en las estimaciones asintóticas de la velocidad de los algoritmos. El algoritmo de Coppersmith-Winograd solo es efectivo en matrices de tamaño astronómico y no se puede aplicar en la práctica.

Conexión con la teoría de grupos (2003)

En 2003, Koch y otros consideraron los algoritmos de Strassen y Coppersmith-Winograd en sus artículos [8] en el contexto de la teoría de grupos . Demostraron que la conjetura de Strassen es válida (es decir, la complejidad mínima está acotada para cualquier ) si se cumple una de las hipótesis de la teoría de grupos [9] .

{\ estilo de visualización O (n ^ {2 + \ épsilon})}

\epsilon

Potencias de matrices

Las matrices cuadradas se pueden multiplicar por sí mismas muchas veces de la misma forma que los números ordinarios, ya que tienen el mismo número de filas y columnas. Tal multiplicación secuencial se puede llamar elevar una matriz a una potencia ; este será un caso especial de la multiplicación habitual de varias matrices. Las matrices rectangulares tienen un número diferente de filas y columnas, por lo que nunca se pueden elevar a una potencia. Una matriz A de n × n elevada a una potencia se define mediante la fórmula

{\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k))

y tiene las siguientes propiedades ( λ es un escalar):

Grado cero:

\mathbf{A} ^{0}=\mathbf{E}

donde E es la matriz identidad . Esto es análogo al hecho de que la potencia cero de cualquier número es igual a uno.

Multiplicación por un escalar:

(\lambda \mathbf {A} )^{k}=\lambda ^{k}\mathbf {A} ^{k}

Determinante:

\det(\mathbf {A} ^{k})=\det(\mathbf {A} )^{k}

La forma más sencilla de calcular el grado de una matriz es multiplicar la matriz Ak por el resultado de la multiplicación anterior, partiendo de la matriz identidad, como se suele hacer con los escalares. Para matrices diagonalizables , existe un mejor método basado en utilizar la descomposición espectral de la matriz A. Otro método, basado en el teorema de Hamilton-Cayley , construye una expresión más eficiente para Ak , en la que el escalar se eleva a la potencia requerida , y no a toda la matriz .

Las matrices diagonales constituyen un caso especial . Dado que el producto de matrices diagonales se reduce a la multiplicación de los elementos diagonales correspondientes, entonces la k -ésima potencia de la matriz diagonal A consiste en los elementos elevados a la potencia requerida:

\mathbf {A} ^{k}={\begin{pmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0& \cdots &a_{nn}\end{pmatrix}}^{k}={\begin{pmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\ \\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{pmatrix}}.

Así, no es difícil elevar una matriz diagonal a una potencia. Al elevar una matriz arbitraria (no necesariamente diagonal) a una potencia, a menudo es útil usar primero las propiedades de las matrices diagonalizables .

Usando la multiplicación de matrices y la exponenciación de matrices, se pueden definir otras operaciones sobre matrices. Por ejemplo, el exponente de la matriz se puede definir en términos de una serie de potencias , el logaritmo de la matriz se puede definir como el inverso del exponente de la matriz , y así sucesivamente.

Véase también

Literatura

Korn G., Korn T. Matrix Algebra y Matrix Calculus // Manual de Matemáticas. - 4ª edición. - M. : Nauka, 1978. - S. 392-394.

Notas

↑ Colección cibernética. Series nuevas. Tema. 25. Sáb. artículos 1983 - 1985: Per. De inglés. - M.: Mir, 1988 - V.B. Aleksev. Complejidad de la multiplicación de matrices. Revisar.
↑ Strassen V. La eliminación gaussiana no es óptima // Numer . Matemáticas / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, edición. 4.- Pág. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
↑ Pan V. Ya, el algoritmo de Strassen no es óptimo: técnica trilineal de agregar, unir y cancelar para construir algoritmos rápidos para operaciones matriciales. — Proc. 19º Simposio Anual sobre Fundamentos de Ciencias de la Computación, Ann Arbor, Michigan, 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — complejidad para la multiplicación aproximada de matrices. - informar. proceso. Lett., 1979 $O(n^{2.7799})$
↑ Schonhage A. Multiplicación de matrices parcial y total. — SIAM J. Cómputo., 1981
↑ Don Coppersmith y Shmuel Winograd. Multiplicación de matrices mediante progresiones aritméticas. Revista de Computación Simbólica , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplying matices in O(n 2.3727 time ). Archivado el 26 de octubre de 2014 en Wayback Machine .
↑ Algoritmos de teoría de grupos para la multiplicación de matrices . Consultado el 26 de septiembre de 2009. Archivado desde el original el 6 de agosto de 2011. (indefinido)
↑ Hacia un algoritmo óptimo para la multiplicación de matrices (enlace descendente) . Consultado el 26 de septiembre de 2009. Archivado desde el original el 31 de marzo de 2010. (indefinido)

Vectores y matrices

Vectores

Conceptos básicos	Vector en geometría Base base ortogonal Coordenadas vectoriales colinealidad ortogonalidad Dependencia lineal Espacio de columna
Tipos de vectores	Vector unitario vector axial vector isotrópico Normal colinealidad vector cero Vector de radio Vector propio
Operaciones sobre vectores	producto escalar producto vectorial producto mixto Producto pseudoescalar Producto cruzado doble
Tipos de espacio	espacio vectorial espacio afín espacio euclidiano Espacio pseudo-euclidiano espacio normado espacio minkowski

matrices

Conceptos básicos	Multiplicación de matrices matriz transpuesta Matriz conjugada hermítica Matriz simétrica matriz inversa valor propio Polinomio característico de una matriz
Matrices especiales	Matriz de identidad Matriz cero Matriz diagonal matriz lambda
Descomposiciones de matrices	descomposición LU Descomposición de Cholesky descomposición QR descomposición LUP valor singular de descomposición Descomposición espectral de una matriz

Otro