Editing Matrix multiplication (section)

===Associativity===
Given three matrices {{math|'''A''', '''B'''}} and {{math|'''C'''}}, the products {{math|('''AB''')'''C'''}} and {{math|'''A'''('''BC''')}} are defined if and only if the number of columns of {{math|'''A'''}} equals the number of rows of {{math|'''B'''}}, and the number of columns of {{math|'''B'''}} equals the number of rows of {{math|'''C'''}} (in particular, if one of the products is defined, then the other is also defined). In this case, one has the [[associative property]]
:<math>(\mathbf{AB})\mathbf{C}=\mathbf{A}(\mathbf{BC}).</math>

As for any associative operation, this allows omitting parentheses, and writing the above products as {{tmath|\mathbf{ABC}.}}

This extends naturally to the product of any number of matrices provided that the dimensions match. That is, if {{math|'''A'''<sub>1</sub>, '''A'''<sub>2</sub>, ..., '''A'''<sub>''n''</sub>}} are matrices such that the number of columns of {{math|'''A'''<sub>''i''</sub>}} equals the number of rows of {{math|'''A'''<sub>''i'' + 1</sub>}} for {{math|1=''i'' = 1, ..., ''n'' – 1}}, then the product 
:<math> \prod_{i=1}^n \mathbf{A}_i = \mathbf{A}_1\mathbf{A}_2\cdots\mathbf{A}_n </math>
is defined and does not depend on the [[order of operations|order of the multiplications]], if the order of the matrices is kept fixed.

These properties may be proved by straightforward but complicated [[summation]] manipulations. This result also follows from the fact that matrices represent [[linear map]]s. Therefore, the associative property of matrices is simply a specific case of the associative property of [[function composition]].

====Computational complexity depends on parenthesization====
Although the result of a sequence of matrix products does not depend on the [[order of operation]] (provided that the order of the matrices is not changed), the [[computational complexity]] may depend dramatically on this order.

For example, if {{math|'''A''', '''B'''}} and {{math|'''C'''}} are matrices of respective sizes {{math|10×30, 30×5, 5×60}}, computing {{math|('''AB''')'''C'''}} needs {{math|1=10×30×5 + 10×5×60 = 4,500}} multiplications, while computing {{math|'''A'''('''BC''')}} needs {{math|1=30×5×60 + 10×30×60 = 27,000}} multiplications.

Algorithms have been designed for choosing the best order of products; see [[Matrix chain multiplication]]. When the number {{mvar|n}} of matrices increases, it has been shown that the choice of the best order has a complexity of <math>O(n \log n).</math><ref>{{cite journal
  | last1 = Hu
  | first1 = T. C. | author1-link = T. C. Hu
  | last2 = Shing
  | first2 = M.-T.
  | title = Computation of Matrix Chain Products, Part I
  | journal = SIAM Journal on Computing
  | volume = 11
  | issue = 2
  | pages = 362–373
  | year = 1982
  | url = http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0211028.pdf
  | issn = 0097-5397
  | doi=10.1137/0211028
  | citeseerx = 10.1.1.695.2923
  }}
</ref><ref>{{cite journal
  | last1 = Hu
  | first1 = T. C. | author1-link = T. C. Hu
  | last2 = Shing
  | first2 = M.-T.
  | title = Computation of Matrix Chain Products, Part II
  | journal = SIAM Journal on Computing
  | volume = 13
  | issue = 2
  | pages = 228–251
  | year = 1984
  | url = http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0213017.pdf
  | issn = 0097-5397
  | doi=10.1137/0213017
  | citeseerx = 10.1.1.695.4875
  }}
</ref>

====Application to similarity====
Any [[invertible matrix]] <math>\mathbf{P}</math> defines a [[similar matrix|similarity transformation]] (on square matrices of the same size as <math>\mathbf{P}</math>)
:<math>S_\mathbf{P}(\mathbf{A}) = \mathbf{P}^{-1} \mathbf{A} \mathbf{P}.</math>

Similarity transformations map product to products, that is 
:<math>S_\mathbf{P}(\mathbf{AB}) = S_\mathbf{P}(\mathbf{A})S_\mathbf{P}(\mathbf{B}).</math>

In fact, one has 
:<math>\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}).</math>