Multiplicación de matrices

Operación matemática en álgebra lineal.

Para la multiplicación de matrices, el número de columnas de la primera matriz debe ser igual al número de filas de la segunda matriz. La matriz resultante tiene el número de filas de la primera y el número de columnas de la segunda matriz.

En matemáticas , particularmente en álgebra lineal , la multiplicación de matrices es una operación binaria que produce una matriz a partir de dos matrices. Para la multiplicación de matrices, el número de columnas de la primera matriz debe ser igual al número de filas de la segunda matriz. La matriz resultante, conocida como producto matricial , tiene el número de filas de la primera y el número de columnas de la segunda matriz. El producto de las matrices A y B se denota como AB . ^[1]

La multiplicación de matrices fue descrita por primera vez por el matemático francés Jacques Philippe Marie Binet en 1812, ^[2] para representar la composición de aplicaciones lineales que se representan mediante matrices. La multiplicación de matrices es, por tanto, una herramienta básica del álgebra lineal y, como tal, tiene numerosas aplicaciones en muchas áreas de las matemáticas, así como en matemáticas aplicadas , estadística , física , economía e ingeniería . ^{[3] [4]} Computar productos matriciales es una operación central en todas las aplicaciones computacionales del álgebra lineal.

Notación

Este artículo utilizará las siguientes convenciones de notación: las matrices se representan con letras mayúsculas en negrita, por ejemplo, A ; vectores en minúsculas y negrita, por ejemplo, a ; y las entradas de vectores y matrices están en cursiva (son números de un campo), por ejemplo, A y a . La notación de índice suele ser la forma más clara de expresar definiciones y se utiliza como estándar en la literatura. La entrada en la fila i , columna j de la matriz A se indica mediante ( A ) _ij , A _ij o a _ij . Por el contrario, se utiliza un único subíndice, por ejemplo A ₁ , A ₂ , para seleccionar una matriz (no una entrada de matriz) de una colección de matrices.

Definición

Si A es una matriz m × n y B es una matriz n × p ,

$${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}b_{11}&b_{12}&\cdots &b_{1p}\\b_{21}&b_{22}&\cdots &b_{2p}\\\vdots &\vdots &\ddots &\vdots \\b_{n1}&b_{n2}&\cdots &b_{np}\\\end{pmatrix}}}$$

producto matricial C = ABm × p ^{[5] [6] [7] [8]}

$${\displaystyle \mathbf {C} ={\begin{pmatrix}c_{11}&c_{12}&\cdots &c_{1p}\\c_{21}&c_{22}&\cdots &c_{2p}\\\vdots &\vdots &\ddots &\vdots \\c_{m1}&c_{m2}&\cdots &c_{mp}\\\end{pmatrix}}}$$

$${\displaystyle c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj},}$$

i = 1, ..., mj = 1, ..., p

Es decir, la entrada del producto se obtiene multiplicando término por término las entradas de la i -ésima fila de A y la j -ésima columna de B , y sumando estos n productos. En otras palabras, es el producto escalar de la i- ésima fila de A y la j- ésima columna de B. ${\displaystyle c_{ij}}$ ${\displaystyle c_{ij}}$

Por lo tanto, AB también se puede escribir como

$${\displaystyle \mathbf {C} ={\begin{pmatrix}a_{11}b_{11}+\cdots +a_{1n}b_{n1}&a_{11}b_{12}+\cdots +a_{1n}b_{n2}&\cdots &a_{11}b_{1p}+\cdots +a_{1n}b_{np}\\a_{21}b_{11}+\cdots +a_{2n}b_{n1}&a_{21}b_{12}+\cdots +a_{2n}b_{n2}&\cdots &a_{21}b_{1p}+\cdots +a_{2n}b_{np}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}b_{11}+\cdots +a_{mn}b_{n1}&a_{m1}b_{12}+\cdots +a_{mn}b_{n2}&\cdots &a_{m1}b_{1p}+\cdots +a_{mn}b_{np}\\\end{pmatrix}}}$$

Así, el producto AB se define si y sólo si el número de columnas en A es igual al número de filas en B , ^[1] en este caso n .

En la mayoría de los escenarios, las entradas son números, pero pueden ser cualquier tipo de objetos matemáticos para los cuales se definen una suma y una multiplicación, que sean asociativos y tales que la suma sea conmutativa y la multiplicación sea distributiva con respecto a la suma. . En particular, las entradas pueden ser matrices en sí mismas (ver matriz de bloques ).

Ilustración

La figura de la derecha ilustra esquemáticamente el producto de dos matrices A y B , mostrando cómo cada intersección en la matriz del producto corresponde a una fila de A y una columna de B.

$${\displaystyle {\overset {4\times 2{\text{ matrix}}}{\begin{bmatrix}a_{11}&a_{12}\\\cdot &\cdot \\a_{31}&a_{32}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &b_{12}&b_{13}\\\cdot &b_{22}&b_{23}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &c_{12}&\cdot \\\cdot &\cdot &\cdot \\\cdot &\cdot &c_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}}$$

Los valores en las intersecciones, marcados con círculos en la figura de la derecha, son:

$${\displaystyle {\begin{aligned}c_{12}&=a_{11}b_{12}+a_{12}b_{22}\\c_{33}&=a_{31}b_{13}+a_{32}b_{23}\end{aligned}}}$$

Aplicaciones fundamentales

Históricamente, la multiplicación de matrices se ha introducido para facilitar y aclarar los cálculos en álgebra lineal . Esta fuerte relación entre la multiplicación de matrices y el álgebra lineal sigue siendo fundamental en todas las matemáticas, así como en física , química , ingeniería e informática .

mapas lineales

Si un espacio vectorial tiene una base finita , cada uno de sus vectores está representado de forma única por una secuencia finita de escalares, llamada vector de coordenadas , cuyos elementos son las coordenadas del vector sobre la base. Estos vectores de coordenadas forman otro espacio vectorial, que es isomorfo al espacio vectorial original. Un vector de coordenadas se organiza comúnmente como una matriz de columnas (también llamada vector de columnas ), que es una matriz con una sola columna. Entonces, un vector columna representa tanto un vector de coordenadas como un vector del espacio vectorial original.

Un mapa lineal A desde un espacio vectorial de dimensión n a un espacio vectorial de dimensión m mapea un vector columna

${\displaystyle \mathbf {x} ={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}}$

sobre el vector de columna

${\displaystyle \mathbf {y} =A(\mathbf {x} )={\begin{pmatrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}}.}$

La aplicación lineal A está definida así por la matriz

${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},}$

y asigna el vector de columna al producto de la matriz ${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {y} =\mathbf {Ax} .}$

Si B es otro mapa lineal del espacio vectorial anterior de dimensión m , a un espacio vectorial de dimensión p , se representa mediante una matriz. Un cálculo sencillo muestra que la matriz del mapa compuesto es el producto matricial (la fórmula general ) que define la composición de la función se instancia aquí como un caso específico de asociatividad del producto matricial (ver § Asociatividad a continuación): ${\displaystyle p\times m}$ ${\displaystyle \mathbf {B} .}$ ${\displaystyle B\circ A}$ ${\displaystyle \mathbf {BA} .}$ ${\displaystyle (B\circ A)(\mathbf {x} )=B(A(\mathbf {x} ))}$

${\displaystyle (\mathbf {BA} )\mathbf {x} =\mathbf {B} (\mathbf {Ax} )=\mathbf {BAx} .}$

Rotaciones geométricas

Usando un sistema de coordenadas cartesiano en un plano euclidiano, la rotación en un ángulo alrededor del origen es un mapa lineal. Más precisamente, ${\displaystyle \alpha }$

$${\displaystyle {\begin{bmatrix}x'\\y'\end{bmatrix}}={\begin{bmatrix}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}},}$$

${\displaystyle (x,y)}$ ${\displaystyle (x',y')}$

La composición de la rotación por y que por entonces corresponde al producto de la matriz. ${\displaystyle \alpha }$ ${\displaystyle \beta }$

$${\displaystyle {\begin{bmatrix}\cos \beta &-\sin \beta \\\sin \beta &\cos \beta \end{bmatrix}}{\begin{bmatrix}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{bmatrix}}={\begin{bmatrix}\cos \beta \cos \alpha -\sin \beta \sin \alpha &-\cos \beta \sin \alpha -\sin \beta \cos \alpha \\\sin \beta \cos \alpha +\cos \beta \sin \alpha &-\sin \beta \sin \alpha +\cos \beta \cos \alpha \end{bmatrix}}={\begin{bmatrix}\cos(\alpha +\beta )&-\sin(\alpha +\beta )\\\sin(\alpha +\beta )&\cos(\alpha +\beta )\end{bmatrix}},}$$

identidades trigonométricas apropiadas para la segunda igualdad. ${\displaystyle \alpha +\beta }$

Asignación de recursos en economía.

El cálculo de la entrada inferior izquierda corresponde a la consideración de todos los caminos (resaltados) desde el producto básico hasta el producto final en el gráfico de flujo de producción. ${\displaystyle \mathbf {AB} }$ ${\displaystyle b_{4}}$ ${\displaystyle f_{1}}$

Por ejemplo, una fábrica ficticia utiliza 4 tipos de productos básicos para producir 3 tipos de bienes intermedios , que a su vez se utilizan para producir 3 tipos de productos finales . las matrices ${\displaystyle b_{1},b_{2},b_{3},b_{4}}$ ${\displaystyle m_{1},m_{2},m_{3}}$ ${\displaystyle f_{1},f_{2},f_{3}}$

${\displaystyle \mathbf {A} ={\begin{pmatrix}1&0&1\\2&1&1\\0&1&1\\1&1&2\\\end{pmatrix}}}$   y   ${\displaystyle \mathbf {B} ={\begin{pmatrix}1&2&1\\2&3&1\\4&2&2\\\end{pmatrix}}}$

Proporcionan la cantidad de productos básicos necesarios para una determinada cantidad de bienes intermedios y la cantidad de bienes intermedios necesarios para una determinada cantidad de productos finales, respectivamente. Por ejemplo, para producir una unidad de bien intermedio , una unidad de producto básico , dos unidades de , no se necesitan unidades de y una unidad de , correspondiente a la primera columna de . ${\displaystyle m_{1}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle b_{3}}$ ${\displaystyle b_{4}}$ ${\displaystyle \mathbf {A} }$

Usando la multiplicación de matrices, calcule

${\displaystyle \mathbf {AB} ={\begin{pmatrix}5&4&3\\8&9&5\\\ 6&5&3\\11&9&6\\\end{pmatrix}};}$

esta matriz proporciona directamente las cantidades de productos básicos necesarios para determinadas cantidades de bienes finales. Por ejemplo, la entrada inferior izquierda de se calcula como , lo que refleja que se necesitan unidades de para producir una unidad de . De hecho, se necesita una unidad para , una para cada dos y para cada una de las cuatro unidades que van en la unidad, ver imagen. ${\displaystyle \mathbf {AB} }$ ${\displaystyle 1\cdot 1+1\cdot 2+2\cdot 4=11}$ ${\displaystyle 11}$ ${\displaystyle b_{4}}$ ${\displaystyle f_{1}}$ ${\displaystyle b_{4}}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle 2}$ ${\displaystyle m_{3}}$ ${\displaystyle f_{1}}$

Para producir, por ejemplo, 100 unidades del producto final , 80 unidades de y 60 unidades de , las cantidades necesarias de bienes básicos se pueden calcular como ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{3}}$

${\displaystyle (\mathbf {AB} ){\begin{pmatrix}100\\80\\60\\\end{pmatrix}}={\begin{pmatrix}1000\\1820\\1180\\2180\end{pmatrix}},}$

es decir, se necesitan unidades de , unidades de , unidades de , unidades de . De manera similar, la matriz de productos se puede utilizar para calcular las cantidades necesarias de bienes básicos para otros datos sobre cantidades de bienes finales. ^[9] ${\displaystyle 1000}$ ${\displaystyle b_{1}}$ ${\displaystyle 1820}$ ${\displaystyle b_{2}}$ ${\displaystyle 1180}$ ${\displaystyle b_{3}}$ ${\displaystyle 2180}$ ${\displaystyle b_{4}}$ ${\displaystyle \mathbf {AB} }$

Sistema de ecuaciones lineales.

La forma general de un sistema de ecuaciones lineales es

${\displaystyle {\begin{matrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}=b_{2}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{matrix}}.}$

Usando la misma notación anterior, dicho sistema es equivalente a la ecuación matricial única

${\displaystyle \mathbf {Ax} =\mathbf {b} .}$

Producto escalar, forma bilineal y forma sesquilineal

El producto escalar de dos vectores columna es la entrada única del producto matricial

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {y} ,}$

¿Dónde está el vector fila obtenido al transponer ? (Como es habitual, una matriz de 1×1 se identifica con su entrada única). ${\displaystyle \mathbf {x} ^{\mathsf {T}}}$ ${\displaystyle \mathbf {x} }$

De manera más general, cualquier forma bilineal sobre un espacio vectorial de dimensión finita puede expresarse como un producto matricial.

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {Ay} ,}$

y cualquier forma sesquilineal puede expresarse como

${\displaystyle \mathbf {x} ^{\dagger }\mathbf {Ay} ,}$

donde denota la transpuesta conjugada de (conjugado de la transpuesta, o equivalentemente transpuesta del conjugado). ${\displaystyle \mathbf {x} ^{\dagger }}$ ${\displaystyle \mathbf {x} }$

Propiedades generales

La multiplicación de matrices comparte algunas propiedades con la multiplicación habitual . Sin embargo, la multiplicación de matrices no está definida si el número de columnas del primer factor difiere del número de filas del segundo factor, y es no conmutativa , ^[10] incluso cuando el producto permanece definido después de cambiar el orden de los factores. . ^{[11] [12]}

No conmutatividad

Una operación es conmutativa si, dados dos elementos A y B tales que el producto está definido, entonces también está definido, y ${\displaystyle \mathbf {A} \mathbf {B} }$ ${\displaystyle \mathbf {B} \mathbf {A} }$ ${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} .}$

Si A y B son matrices de tamaños respectivos y , entonces se define si , y se define si . Por lo tanto, si uno de los productos está definido, no es necesario definir el otro. Si , los dos productos están definidos, pero tienen tamaños diferentes; por lo tanto no pueden ser iguales. Sólo si , es decir, si A y B son matrices cuadradas del mismo tamaño, ambos son productos definidos y del mismo tamaño. Incluso en este caso, en general se tiene ${\displaystyle m\times n}$ ${\displaystyle p\times q}$ ${\displaystyle \mathbf {A} \mathbf {B} }$ ${\displaystyle n=p}$ ${\displaystyle \mathbf {B} \mathbf {A} }$ ${\displaystyle m=q}$ ${\displaystyle m=q\neq n=p}$ ${\displaystyle m=q=n=p}$

${\displaystyle \mathbf {A} \mathbf {B} \neq \mathbf {B} \mathbf {A} .}$

Por ejemplo

${\displaystyle {\begin{pmatrix}0&1\\0&0\end{pmatrix}}{\begin{pmatrix}0&0\\1&0\end{pmatrix}}={\begin{pmatrix}1&0\\0&0\end{pmatrix}},}$

pero

${\displaystyle {\begin{pmatrix}0&0\\1&0\end{pmatrix}}{\begin{pmatrix}0&1\\0&0\end{pmatrix}}={\begin{pmatrix}0&0\\0&1\end{pmatrix}}.}$

Este ejemplo se puede ampliar para mostrar que, si A es una matriz con entradas en un campo F , entonces para cada matriz B con entradas en F , si y solo si donde , e I es la matriz identidad . Si, en lugar de un campo, se supone que las entradas pertenecen a un anillo , entonces se debe agregar la condición de que c pertenezca al centro del anillo. ${\displaystyle n\times n}$ ${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} }$ ${\displaystyle n\times n}$ ${\displaystyle \mathbf {A} =c\,\mathbf {I} }$ ${\displaystyle c\in F}$ ${\displaystyle n\times n}$

Un caso especial en el que ocurre la conmutatividad es cuando D y E son dos matrices diagonales (cuadradas) (del mismo tamaño); entonces DE = ED . ^[10] Nuevamente, si las matrices están sobre un anillo general en lugar de un campo, las entradas correspondientes en cada una también deben conmutar entre sí para que esto se cumpla.

Distributividad

El producto matricial es distributivo con respecto a la suma de matrices . Es decir, si A , B , C , D son matrices de tamaños respectivos m × n , n × p , n × p y p × q , se tiene (distributividad izquierda)

${\displaystyle \mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ,}$

y (distributividad correcta)

${\displaystyle (\mathbf {B} +\mathbf {C} )\mathbf {D} =\mathbf {BD} +\mathbf {CD} .}$^[10]

Esto resulta de la distributividad de los coeficientes por

${\displaystyle \sum _{k}a_{ik}(b_{kj}+c_{kj})=\sum _{k}a_{ik}b_{kj}+\sum _{k}a_{ik}c_{kj}}$

${\displaystyle \sum _{k}(b_{ik}+c_{ik})d_{kj}=\sum _{k}b_{ik}d_{kj}+\sum _{k}c_{ik}d_{kj}.}$

Producto con escalar

Si A es una matriz y c un escalar, entonces las matrices y se obtienen multiplicando hacia la izquierda o hacia la derecha todas las entradas de A por c . Si los escalares tienen la propiedad conmutativa , entonces ${\displaystyle c\mathbf {A} }$ ${\displaystyle \mathbf {A} c}$ ${\displaystyle c\mathbf {A} =\mathbf {A} c.}$

Si el producto está definido (es decir, el número de columnas de A es igual al número de filas de B ), entonces ${\displaystyle \mathbf {AB} }$

${\displaystyle c(\mathbf {AB} )=(c\mathbf {A} )\mathbf {B} }$y ${\displaystyle (\mathbf {A} \mathbf {B} )c=\mathbf {A} (\mathbf {B} c).}$

Si los escalares tienen la propiedad conmutativa, entonces las cuatro matrices son iguales. De manera más general, los cuatro son iguales si c pertenece al centro de un anillo que contiene las entradas de las matrices, porque en este caso, c X = X c para todas las matrices X .

Estas propiedades resultan de la bilinealidad del producto de escalares:

${\displaystyle c\left(\sum _{k}a_{ik}b_{kj}\right)=\sum _{k}(ca_{ik})b_{kj}}$

${\displaystyle \left(\sum _{k}a_{ik}b_{kj}\right)c=\sum _{k}a_{ik}(b_{kj}c).}$

Transponer

Si los escalares tienen la propiedad conmutativa , la transpuesta de un producto de matrices es el producto, en orden inverso, de las transpuestas de los factores. Eso es

${\displaystyle (\mathbf {AB} )^{\mathsf {T}}=\mathbf {B} ^{\mathsf {T}}\mathbf {A} ^{\mathsf {T}}}$

donde ^T denota la transpuesta, es decir el intercambio de filas y columnas.

Esta identidad no se cumple para las entradas no conmutativas, ya que el orden entre las entradas de A y B se invierte cuando se amplía la definición del producto matricial.

Complejo conjugado

Si A y B tienen entradas complejas , entonces

${\displaystyle (\mathbf {AB} )^{*}=\mathbf {A} ^{*}\mathbf {B} ^{*}}$

donde ^* denota el conjugado complejo de entrada de una matriz.

Esto resulta de aplicar a la definición de producto matricial el hecho de que el conjugado de una suma es la suma de los conjugados de los sumandos y el conjugado de un producto es el producto de los conjugados de los factores.

La transposición actúa sobre los índices de las entradas, mientras que la conjugación actúa de forma independiente sobre las propias entradas. Resulta que, si A y B tienen entradas complejas, se tiene

${\displaystyle (\mathbf {AB} )^{\dagger }=\mathbf {B} ^{\dagger }\mathbf {A} ^{\dagger },}$

donde ^† denota la transpuesta conjugada (conjugado de la transpuesta, o equivalentemente transpuesta del conjugado).

asociatividad

Dadas tres matrices A , B y C , los productos ( AB ) C y A ( BC ) se definen si y sólo si el número de columnas de A es igual al número de filas de B , y el número de columnas de B es igual al número de filas de C (en particular, si uno de los productos está definido, entonces el otro también está definido). En este caso se tiene la propiedad asociativa

${\displaystyle (\mathbf {AB} )\mathbf {C} =\mathbf {A} (\mathbf {BC} ).}$

Como ocurre con cualquier operación asociativa, esto permite omitir paréntesis y escribir los productos anteriores como ${\displaystyle \mathbf {ABC} .}$

Esto se extiende naturalmente al producto de cualquier número de matrices siempre que las dimensiones coincidan. Es decir, si A ₁ , A ₂ , ..., An _son matrices tales que el número de columnas de A _i es igual al número de filas de A _{i + 1} para i = 1, ..., n – 1 , entonces el producto

${\displaystyle \prod _{i=1}^{n}\mathbf {A} _{i}=\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}}$

está definido y no depende del orden de las multiplicaciones , si el orden de las matrices se mantiene fijo.

Estas propiedades pueden demostrarse mediante manipulaciones de suma sencillas pero complicadas . Este resultado también se deriva del hecho de que las matrices representan aplicaciones lineales . Por tanto, la propiedad asociativa de las matrices es simplemente un caso específico de la propiedad asociativa de composición de funciones .

La complejidad computacional depende del paréntesis.

Aunque el resultado de una secuencia de productos matriciales no depende del orden de operación (siempre que no se cambie el orden de las matrices), la complejidad computacional puede depender dramáticamente de este orden.

Por ejemplo, si A , B y C son matrices de tamaños respectivos 10×30, 30×5, 5×60 , calcular ( AB ) C necesita 10×30×5 + 10×5×60 = 4500 multiplicaciones, mientras que calcular A ( BC ) necesita 30×5×60 + 10×30×60 = 27.000 multiplicaciones.

Se han diseñado algoritmos para elegir el mejor orden de productos, consulte Multiplicación de cadenas de matrices . Cuando el número n de matrices aumenta, se ha demostrado que la elección del mejor orden tiene una complejidad de ${\displaystyle O(n\log n).}$

Aplicación a la similitud

Cualquier matriz invertible define una transformación de similitud (en matrices cuadradas del mismo tamaño que ) ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbf {P} }$

${\displaystyle S_{\mathbf {P} }(\mathbf {A} )=\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} .}$

Las transformaciones de similitud asignan un producto a otro, es decir

${\displaystyle S_{\mathbf {P} }(\mathbf {AB} )=S_{\mathbf {P} }(\mathbf {A} )S_{\mathbf {P} }(\mathbf {B} ).}$

De hecho, uno tiene

${\displaystyle \mathbf {P} ^{-1}(\mathbf {AB} )\mathbf {P} =\mathbf {P} ^{-1}\mathbf {A} (\mathbf {P} \mathbf {P} ^{-1})\mathbf {B} \mathbf {P} =(\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} )(\mathbf {P} ^{-1}\mathbf {B} \mathbf {P} ).}$

Matrices cuadradas

Denotemos el conjunto de matrices cuadradas n × n con entradas en un anillo R , que, en la práctica, suele ser un campo . ${\displaystyle {\mathcal {M}}_{n}(R)}$

En , el producto se define para cada par de matrices. Esto forma un anillo , que tiene la matriz identidad I como elemento identidad (la matriz cuyas entradas diagonales son iguales a 1 y todas las demás entradas son 0). Este anillo también es un R -álgebra asociativa . ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$

Si n > 1 , muchas matrices no tienen inverso multiplicativo . Por ejemplo, una matriz tal que todas las entradas de una fila (o columna) sean 0 no tiene inversa. Si existe, la inversa de una matriz A se denota A ⁻¹ y, por lo tanto, verifica

${\displaystyle \mathbf {A} \mathbf {A} ^{-1}=\mathbf {A} ^{-1}\mathbf {A} =\mathbf {I} .}$

Una matriz que tiene inversa es una matriz invertible . En caso contrario, es una matriz singular .

Un producto de matrices es invertible si y sólo si cada factor es invertible. En este caso, se tiene

${\displaystyle (\mathbf {A} \mathbf {B} )^{-1}=\mathbf {B} ^{-1}\mathbf {A} ^{-1}.}$

Cuando R es conmutativo , y, en particular, cuando es un campo, el determinante de un producto es el producto de los determinantes. Como los determinantes son escalares y los escalares conmutan, se tiene, por tanto,

${\displaystyle \det(\mathbf {AB} )=\det(\mathbf {BA} )=\det(\mathbf {A} )\det(\mathbf {B} ).}$

Las otras invariantes matriciales no se comportan tan bien con los productos. Sin embargo, si R es conmutativo, AB y BA tienen la misma traza , el mismo polinomio característico y los mismos valores propios con las mismas multiplicidades. Sin embargo, los vectores propios son generalmente diferentes si AB ≠ BA .

Potencias de una matriz

Se puede elevar una matriz cuadrada a cualquier potencia entera no negativa multiplicándola por sí misma repetidamente de la misma manera que para los números ordinarios. Eso es,

${\displaystyle \mathbf {A} ^{0}=\mathbf {I} ,}$

${\displaystyle \mathbf {A} ^{1}=\mathbf {A} ,}$

${\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k{\text{ times}}}.}$

Calcular la k- ésima potencia de una matriz necesita k – 1 veces el tiempo de una multiplicación de una sola matriz, si se hace con el algoritmo trivial (multiplicación repetida). Como esto puede llevar mucho tiempo, generalmente se prefiere usar la exponenciación elevando al cuadrado , que requiere menos de 2 log ₂ k multiplicaciones de matrices y, por lo tanto, es mucho más eficiente.

Un caso sencillo para la exponenciación es el de una matriz diagonal . Dado que el producto de matrices diagonales equivale simplemente a multiplicar los elementos diagonales correspondientes, la k -ésima potencia de una matriz diagonal se obtiene elevando las entradas a la potencia k :

${\displaystyle {\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}^{k}={\begin{bmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{bmatrix}}.}$

Álgebra abstracta

La definición de producto matricial requiere que las entradas pertenezcan a un semiring y no requiere que la multiplicación de elementos del semiring sea conmutativa . En muchas aplicaciones, los elementos de la matriz pertenecen a un campo, aunque el semianillo tropical también es una opción común para problemas de ruta más corta de gráficos . ^[13] Incluso en el caso de matrices sobre campos, el producto no es conmutativo en general, aunque es asociativo y distributivo sobre la suma de matrices . Las matrices identidad (que son las matrices cuadradas cuyas entradas son cero fuera de la diagonal principal y 1 en la diagonal principal) son elementos identidad del producto matricial. De ello se deduce que las matrices n × n sobre un anillo forman un anillo, que no es conmutativo excepto si n = 1 y el anillo de tierra es conmutativo.

Una matriz cuadrada puede tener una inversa multiplicativa , llamada matriz inversa . En el caso común donde las entradas pertenecen a un anillo conmutativo R , una matriz tiene inversa si y sólo si su determinante tiene inversa multiplicativa en R. El determinante de un producto de matrices cuadradas es el producto de los determinantes de los factores. Las matrices n × n que tienen inversa forman un grupo bajo multiplicación de matrices, cuyos subgrupos se denominan grupos de matrices . Muchos grupos clásicos (incluidos todos los grupos finitos ) son isomorfos a grupos matriciales; este es el punto de partida de la teoría de las representaciones de grupos .

Complejidad computacional

Mejora de las estimaciones del exponente ω a lo largo del tiempo para la complejidad computacional de la multiplicación de matrices ${\displaystyle O(n^{\omega })}$

El algoritmo de multiplicación de matrices que resulta de la definición requiere, en el peor de los casos , multiplicaciones y sumas de escalares para calcular el producto de dos matrices cuadradas de n × n . Su complejidad computacional es, por tanto , en un modelo de cálculo en el que las operaciones escalares toman un tiempo constante. ${\displaystyle n^{3}}$ ${\displaystyle (n-1)n^{2}}$ ${\displaystyle O(n^{3})}$

Sorprendentemente, esta complejidad no es óptima, como lo demostró en 1969 Volker Strassen , quien proporcionó un algoritmo, ahora llamado algoritmo de Strassen , con una complejidad de ^[14] . El algoritmo de Strassen puede ser paralelizado para mejorar aún más el rendimiento. ^[15] En enero de 2024 , el mejor algoritmo de multiplicación de matrices revisado por pares es el de Virginia Vassilevska Williams , Yinzhan Xu, Zixuan Xu y Renfei Zhou y tiene complejidad O ( n ^2.371552 ) . ^{[16] [17]} No se sabe si la multiplicación de matrices se puede realizar en n ^{2 + o(1)} tiempo. ^[18] Esto sería óptimo, ya que se deben leer los elementos de una matriz para poder multiplicarla por otra matriz. ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).}$^[update] ${\displaystyle n^{2}}$

Dado que la multiplicación de matrices forma la base de muchos algoritmos, y muchas operaciones con matrices incluso tienen la misma complejidad que la multiplicación de matrices (hasta una constante multiplicativa), la complejidad computacional de la multiplicación de matrices aparece en todo el álgebra lineal numérica y la informática teórica .

Generalizaciones

Otros tipos de productos de matrices incluyen:

• Multiplicación de matrices de bloques
• Producto de Cracovia , definido como A ∧ B = B ^T A
• Producto interno de Frobenius , el producto escalar de matrices consideradas como vectores o, de manera equivalente, la suma de las entradas del producto de Hadamard.
• Producto de Hadamard de dos matrices del mismo tamaño, dando como resultado una matriz del mismo tamaño, que es el producto entrada por entrada
• Producto de Kronecker o producto tensorial , la generalización a cualquier tamaño del anterior
• Producto Khatri-Rao y producto que parte la cara
• Producto externo , también llamado producto diádico o producto tensorial de matrices de dos columnas, que es ${\displaystyle \mathbf {a} \mathbf {b} ^{\mathsf {T}}}$
• Multiplicación escalar

Ver también

• Cálculo matricial , para la interacción de la multiplicación de matrices con operaciones del cálculo

Notas

1. Nykamp, ​​Duane. "Multiplicación de matrices y vectores". Perspectiva matemática . Consultado el 6 de septiembre de 2020 .
2. O'Connor, John J.; Robertson, Edmund F. , "Jacques Philippe Marie Binet", Archivo MacTutor de Historia de las Matemáticas , Universidad de St Andrews
3. Lerner, RG ; Trigg, GL (1991). Enciclopedia de Física (2ª ed.). Editores VHC. ISBN 978-3-527-26954-9.
4. Parker, CB (1994). Enciclopedia de Física McGraw Hill (2ª ed.). McGraw-Hill. ISBN 978-0-07-051400-3.
5. Lipschutz, S.; Lipson, M. (2009). Álgebra lineal . Esquemas de Schaum (4ª ed.). McGraw Hill (Estados Unidos). págs. 30-31. ISBN 978-0-07-154352-1.
6. Riley, KF; Hobson, diputado; Bence, SJ (2010). Métodos matemáticos para la física y la ingeniería . Prensa de la Universidad de Cambridge. ISBN 978-0-521-86153-3.
7. Adams, RA (1995). Cálculo, un curso completo (3ª ed.). Addison Wesley. pag. 627.ISBN​ 0-201-82823-5.
8. Cuerno, Johnson (2013). Análisis matricial (2ª ed.). Prensa de la Universidad de Cambridge. pag. 6.ISBN​ 978-0-521-54823-6.
9. Peter Stingl (1996). Mathematik für Fachhochschulen – Technik und Informatik (en alemán) (5ª ed.). Múnich : Carl Hanser Verlag . ISBN 3-446-18668-9.Aquí: Exm.5.4.10, p.205-206
10. Weisstein, Eric W. "Multiplicación de matrices". mathworld.wolfram.com . Consultado el 6 de septiembre de 2020 .
11. Lipschutz, S.; Lipson, M. (2009). "2". Álgebra lineal . Esquemas de Schaum (4ª ed.). McGraw Hill (Estados Unidos). ISBN 978-0-07-154352-1.
12. Cuerno, Johnson (2013). "Capítulo 0". Análisis matricial (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 978-0-521-54823-6.
13. Motwani, Rajeev ; Raghavan, Prabhakar (1995). Algoritmos aleatorios. Prensa de la Universidad de Cambridge. pag. 280.ISBN​ 9780521474658.
14. Volker Strassen (agosto de 1969). "La eliminación gaussiana no es óptima". Matemática numérica . 13 (4): 354–356. doi :10.1007/BF02165411. S2CID  121656251.
15. C.-C. Chou y Y.-F. Deng y G. Li y Y. Wang (1995). "Paralelización del método de Strassen para la multiplicación de matrices en arquitecturas MIMD de memoria distribuida" (PDF) . Computadoras Matemáticas. Aplicar . 30 (2): 49–69. doi :10.1016/0898-1221(95)00077-C.
16. Vassilevska Williams, Virginia; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei. Nuevos límites para la multiplicación de matrices: de Alfa a Omega . Actas del Simposio anual ACM-SIAM de 2024 sobre algoritmos discretos (SODA). págs. 3792–3835. arXiv : 2307.07970 . doi :10.1137/1.9781611977912.134.
17. Nadis, Steve (7 de marzo de 2024). "Un nuevo avance acerca la multiplicación de matrices a lo ideal" . Consultado el 9 de marzo de 2024 .
18. es decir, en el tiempo n ^2+f(n) , para alguna función f con f ( n ) → 0 como n →∞

Referencias

• Henry Cohn, Robert Kleinberg , Balázs Szegedy y Chris Umans. Algoritmos de teoría de grupos para la multiplicación de matrices. arXiv : math.GR/0511460. Actas del 46º Simposio anual sobre fundamentos de la informática , 23 a 25 de octubre de 2005, Pittsburgh, PA, IEEE Computer Society, págs.
• Henry Cohn, Chris Umans. Un enfoque teórico de grupos para la multiplicación rápida de matrices. arXiv : math.GR/0307321. Actas del 44º Simposio anual del IEEE sobre fundamentos de la informática , 11 al 14 de octubre de 2003, Cambridge, MA, IEEE Computer Society, págs.
• Calderero, D.; Winograd, S. (1990). "Multiplicación de matrices mediante progresiones aritméticas". J. Computación simbólica . 9 (3): 251–280. doi : 10.1016/s0747-7171(08)80013-2 .
• Cuerno, Roger A.; Johnson, Charles R. (1991), Temas de análisis matricial , Cambridge University Press , ISBN 978-0-521-46713-1
• Knuth, DE , El arte de la programación informática Volumen 2: Algoritmos seminuméricos . Profesional de Addison-Wesley; 3 edición (14 de noviembre de 1997). ISBN 978-0-201-89684-8 . págs.501. 
• Prensa, William H.; Flannery, Brian P.; Teukolsky, Saúl A .; Vetterling, William T. (2007), Recetas numéricas: el arte de la informática científica (3.ª ed.), Cambridge University Press , ISBN 978-0-521-88068-8.
• Ran Raz . Sobre la complejidad del producto matricial. En Actas del trigésimo cuarto simposio anual de ACM sobre Teoría de la informática. Prensa ACM, 2002. doi :10.1145/509907.509932.
• Robinson, Sara, Hacia un algoritmo óptimo para la multiplicación de matrices, SIAM News 38(9), noviembre de 2005. PDF
• Strassen, Volker, La eliminación gaussiana no es óptima , Numer. Matemáticas. 13, pág. 354-356, 1969.
• Styan, George PH (1973), "Productos Hadamard y análisis estadístico multivariado" (PDF) , Álgebra lineal y sus aplicaciones , 6 : 217–240, doi : 10.1016/0024-3795(73)90023-2
• Williams, Virginia Vassilevska (19 de mayo de 2012). "Multiplicar matrices más rápido que el calderero-winograd". Actas del 44º simposio sobre Teoría de la Computación - STOC '12 . ACM. págs. 887–898. CiteSeerX  10.1.1.297.2680 . doi :10.1145/2213977.2214056. ISBN 9781450312455. S2CID  14350287.