stringtranslate.com

Multiplicación de 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 tiene el número de filas de la primera matriz y el número de columnas de la segunda matriz.

En matemáticas , específicamente 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 de matrices , tiene el número de filas de la primera matriz 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 mapas 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 las matemáticas aplicadas , la estadística , la física , la economía y la ingeniería . [3] [4] El cálculo de 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, p. ej. A ; los vectores en negrita minúscula, p. ej . a ; y las entradas de vectores y matrices están en cursiva (son números de un campo), p. ej. A y a . La notación de índice es a menudo 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 solo subíndice, p. ej. A 1 , A 2 , para seleccionar una matriz (no una entrada de matriz) de una colección de matrices.

Definiciones

Matriz por matriz

Si A es una matriz m × n y B es una matriz n × p , el producto matricial C = AB (denotado sin signos de multiplicación ni puntos) se define como la matriz m × p [5] [6] [7] [8] tal que para i = 1, ..., m y j = 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 .

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

Por lo tanto, el producto AB está definido 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 casos, las entradas son números, pero pueden ser cualquier tipo de objeto matemático para el que se definan una suma y una multiplicación, que sean asociativas 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 (véase matriz de bloques ).

Matriz por vector

Un vector de longitud puede verse como un vector columna , correspondiente a una matriz cuyas entradas están dadas por Si es una matriz, el producto matriz-vector denotado por es entonces el vector que, visto como un vector columna, es igual a la matriz. En notación de índice, esto equivale a:

Una forma de ver esto es que los cambios del vector "simple" al vector de columna y viceversa se asumen y se dejan implícitos.

Matriz de multiplicación por vector

De manera similar, un vector de longitud puede considerarse como un vector fila , correspondiente a una matriz. Para dejar en claro que se trata de un vector fila, en este contexto se suele representar como la transpuesta de un vector columna; por lo tanto, se verán notaciones como La identidad se cumple. En la notación de índice, si es una matriz, equivale a:

Vector por vector

El producto escalar de dos vectores de igual longitud es igual al valor único de la matriz resultante de multiplicar estos vectores como un vector fila y un vector columna, es decir: (o que da como resultado la misma matriz).

Ilustración

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

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

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 y ciencias de la computación .

Mapas lineales

Si un espacio vectorial tiene una base finita , sus vectores están representados 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 columna (también llamada vector columna ), que es una matriz con una sola columna. Por lo tanto, un vector columna representa tanto un vector de coordenadas como un vector del espacio vectorial original.

Una aplicación lineal A de un espacio vectorial de dimensión n en un espacio vectorial de dimensión m asigna un vector columna

sobre el vector columna

La función lineal A queda definida entonces por la matriz

y asigna el vector columna al producto matricial

Si B es otra función lineal del espacio vectorial precedente de dimensión m , en un espacio vectorial de dimensión p , se representa mediante una matriz Un cálculo sencillo muestra que la matriz de la función compuesta es el producto de matrices La fórmula general ) que define la composición de funciones se ejemplifica aquí como un caso específico de asociatividad del producto de matrices (véase § Asociatividad a continuación ):

Rotaciones geométricas

Utilizando un sistema de coordenadas cartesianas en un plano euclidiano, la rotación en un ángulo alrededor del origen es una función lineal. Más precisamente, donde el punto de origen y su imagen se escriben como vectores de columna.

La composición de la rotación por y la de corresponde entonces al producto matricial donde se emplean identidades trigonométricas apropiadas para la segunda igualdad. Es decir, la composición corresponde a la rotación por el ángulo , como se esperaba.

Asignación de recursos en economía

El cálculo de la entrada inferior izquierda corresponde a la consideración de todas las rutas (resaltadas) desde el producto básico hasta el producto final en el gráfico de flujo de producción.

A modo de 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

  y  

Proporcionar la cantidad de productos básicos necesarios para una cantidad dada de bienes intermedios y la cantidad de bienes intermedios necesarios para una cantidad dada de productos finales, respectivamente. Por ejemplo, para producir una unidad de bien intermedio , se necesitan una unidad de producto básico , dos unidades de , ninguna unidad de , y una unidad de , correspondientes a la primera columna de .

Usando la multiplicación de matrices, calcule

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 uno de dos , y para cada una de las cuatro unidades que componen la unidad, véase la imagen.

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

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 de cantidades de bienes finales. [9]

Sistema de ecuaciones lineales

La forma general de un sistema de ecuaciones lineales es

Usando la misma notación que arriba, tal sistema es equivalente a la ecuación de matriz única.

Producto escalar, forma bilineal y forma sesquilineal

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

donde es el vector fila obtenido al transponer . (Como es habitual, una matriz 1×1 se identifica con su entrada única).

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

y cualquier forma sesquilínea puede expresarse como

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

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

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, el otro no necesita estar definido. Si , los dos productos están definidos, pero tienen tamaños diferentes; por lo tanto, no pueden ser iguales. Solo si , es decir, si A y B son matrices cuadradas del mismo tamaño, ambos productos están definidos y son del mismo tamaño. Incluso en este caso, en general se tiene

Por ejemplo

pero

Este ejemplo puede ampliarse 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 pertenece al centro del anillo.

Un caso especial en el que ocurre 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 de matrices 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 por la izquierda)

y (distributividad derecha)

[10]

Esto resulta de la distributividad de los coeficientes por

Producto con un escalar

Si A es una matriz y c un escalar, entonces las matrices y se obtienen multiplicando por la izquierda o por la derecha todas las entradas de A por c . Si los escalares tienen la propiedad conmutativa , entonces

Si el producto está definido (es decir, el número de columnas de A es igual al número de filas de B ), entonces

y

Si los escalares tienen la propiedad conmutativa, entonces las cuatro matrices son iguales. En términos más generales, las 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:

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. Es decir

donde T denota la transposición, es decir el intercambio de filas y columnas.

Esta identidad no se cumple para 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.

Conjugado complejo

Si A y B tienen entradas complejas , entonces

donde * denota el conjugado complejo entrada por 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 independientemente sobre las entradas mismas. Resulta que, si A y B tienen entradas complejas, se tiene

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

Asociatividad

Dadas tres matrices A , B y C , los productos ( AB ) C y A ( BC ) están definidos si y solo 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 lo está). En este caso, se tiene la propiedad asociativa

Como ocurre con cualquier operación asociativa, esto permite omitir los paréntesis y escribir los productos anteriores como ⁠ ⁠

Esto se extiende naturalmente al producto de cualquier número de matrices siempre que las dimensiones coincidan. Es decir, si A 1 , A 2 , ..., A n 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

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

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

La complejidad computacional depende de los paréntesis

Aunque el resultado de una secuencia de productos matriciales no depende del orden de operación (siempre que no se modifique 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; véase 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 [13] [14]

Aplicación a la semejanza

Cualquier matriz invertible define una transformación de similitud (en matrices cuadradas del mismo tamaño que )

Las transformaciones de similitud asignan productos a productos, es decir

De hecho, uno tiene

Matrices cuadradas

Denotemos el conjunto de matrices cuadradas n × n con entradas en un anillo R , que, en la práctica, suele ser un cuerpo .

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

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

Una matriz que tiene una 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

Cuando R es conmutativa y, en particular, cuando es un cuerpo, el determinante de un producto es el producto de los determinantes. Como los determinantes son escalares y los escalares conmutan, se tiene entonces

Los demás invariantes matriciales no se comportan tan bien con los productos. Sin embargo, si R es conmutativa, 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 ABBA .

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 se hace con los números ordinarios. Es decir,

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

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

Álgebra abstracta

La definición de producto matricial requiere que las entradas pertenezcan a un semianillo, y no requiere que la multiplicación de elementos del semianillo sea conmutativa . En muchas aplicaciones, los elementos de la matriz pertenecen a un cuerpo, aunque el semianillo tropical también es una opción común para problemas de ruta más corta de grafos. [15] Incluso en el caso de matrices sobre cuerpos, el producto no es conmutativo en general, aunque es asociativo y es 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 es no conmutativo excepto si n = 1 y el anillo base es conmutativo.

Una matriz cuadrada puede tener una inversa multiplicativa , llamada matriz inversa . En el caso común en el que las entradas pertenecen a un anillo conmutativo R , una matriz tiene una inversa si y solo si su determinante tiene una 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 una inversa forman un grupo bajo la multiplicación de matrices, cuyos subgrupos se denominan grupos matriciales . Muchos grupos clásicos (incluidos todos los grupos finitos ) son isomorfos a los grupos matriciales; este es el punto de partida de la teoría de las representaciones de grupos .

Las matrices son los morfismos de una categoría , la categoría de matrices . Los objetos son los números naturales que miden el tamaño de las matrices, y la composición de los morfismos es la multiplicación de matrices. La fuente de un morfismo es el número de columnas de la matriz correspondiente, y el destino es el número de filas.

Complejidad computacional

Mejora de las estimaciones del exponente ω a lo largo del tiempo para la complejidad computacional de la multiplicación de matrices

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 n × n . Su complejidad computacional es , por tanto , ⁠ , en un modelo de cálculo para el que las operaciones escalares toman un tiempo constante.

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 [16] El algoritmo de Strassen se puede paralelizar para mejorar aún más el rendimiento. [17] A 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 una complejidad de O ( n 2,371552 ) . [18] [19] No se sabe si la multiplicación de matrices se puede realizar en n 2 + o(1) tiempo. [20] Esto sería óptimo, ya que uno debe leer los elementos de una matriz para multiplicarla con otra matriz.

Dado que la multiplicación de matrices constituye la base de muchos algoritmos, y muchas operaciones sobre 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:

Véase también

Notas

  1. ^ de Nykamp, ​​Duane. "Multiplicación de matrices y vectores". Math Insight . Consultado el 6 de septiembre de 2020 .
  2. ^ O'Connor, John J.; Robertson, Edmund F. , "Jacques Philippe Marie Binet", Archivo de Historia de las Matemáticas de MacTutor , Universidad de St Andrews
  3. ^ Lerner, RG ; Trigg, GL (1991). Enciclopedia de Física (2.ª ed.). Editorial VHC. ISBN 978-3-527-26954-9.
  4. ^ Parker, CB (1994). Enciclopedia de Física McGraw Hill (2.ª edición). 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, MP; Bence, SJ (2010). Métodos matemáticos para la física y la ingeniería . Cambridge University Press. ISBN 978-0-521-86153-3.
  7. ^ Adams, RA (1995). Cálculo, un curso completo (3.ª ed.). Addison Wesley. pág. 627. ISBN 0-201-82823-5.
  8. ^ Horn, Johnson (2013). Análisis de matrices (2.ª ed.). Cambridge University Press. pág. 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. ^ abc 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. ^ Horn, Johnson (2013). "Capítulo 0". Análisis de matrices (2.ª ed.). Cambridge University Press. ISBN 978-0-521-54823-6.
  13. ^ Hu, TC ; Shing, M.-T. (1982). "Cálculo de productos de cadenas matriciales, parte I" (PDF) . Revista SIAM de informática . 11 (2): 362–373. CiteSeerX 10.1.1.695.2923 . doi :10.1137/0211028. ISSN  0097-5397. 
  14. ^ Hu, TC ; Shing, M.-T. (1984). "Cálculo de productos de cadenas matriciales, parte II" (PDF) . Revista SIAM de informática . 13 (2): 228–251. CiteSeerX 10.1.1.695.4875 . doi :10.1137/0213017. ISSN  0097-5397. 
  15. ^ Motwani, Rajeev ; Raghavan, Prabhakar (1995). Algoritmos aleatorios. Cambridge University Press. pág. 280. ISBN 9780521474658.
  16. ^ 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.
  17. ^ 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) . Computers Math. Applic . 30 (2): 49–69. doi :10.1016/0898-1221(95)00077-C.
  18. ^ 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.
  19. ^ Nadis, Steve (7 de marzo de 2024). «Un nuevo avance acerca la multiplicación de matrices al ideal» . Consultado el 9 de marzo de 2024 .
  20. ^ es decir, en el tiempo n 2+f(n) , para alguna función f con f ( n ) → 0 cuando n →∞

Referencias