<p>======  Matrix Multiplication  ======</p>

<p>=====  Introduction  =====</p>

<p>====  Prerequisites  ====
It is assumed that those reading this have a basic understanding of what a matrix
is and [[Matrix Addition|how to add them]], and multiply them by scalars, i.e. plain old numbers like 3, or -5.
A secondary school algebra course would probably give one more than enough background,
but is surely not required by any means.</p>

<p>If you need some background [[http://en.wikipedia.org/wiki/Matrix_%28mathematics%29|Go here]]</p>

<p>====  Matrix Multiplication Basics  ====
In order to multiply 2 matrices given one must have the same amount of rows that the other has columns.  In other words two matrices can be multiplied only if one is of dimension m×n and the other is of dimension n×p where m, n, and p are natural numbers {m,n,p  <math>in mathbb{N}</math>}.  The resulting matrix will be of dimension n×n.</p>

<p>===  Example 4x2 Multiplied by 2x4  ===
Take a matrix 4x2 call it <math>mathbf{A}</math>;  another of dimension 2x4 and call it <math>mathbf{B}</math>.  Give them some arbitrary values
and lets do some multiplication.</p>

<math>
 mathbf{A} = begin{bmatrix}
     2 & 3 & -1 & 0  \ 
     -7 & 2 & 1 & 10  
  end{bmatrix}
  mathbf{B} = begin{bmatrix}
     3 & 4    \ 
     2 & 1    \
     -1 & 2   \
     2  & 7    
  end{bmatrix} 
</math>

<p>Our result matrix is going to be 2×2 as you will see as we go step by step.  First
we multiply and sum the first row with the first column:  2(3) + 3(2) + (-1)(-1) + 0(2). 
Then we do the same for the first row and second column:  2(4) + 3(1) + (-1)(2)+ 0(7), etc.</p>

<p>To make a long story short, our matrix would be:</p>

<math>
mathbf{AB} = begin{bmatrix}
     2(3) + 3(2) + (-1)(-1) +  0(2) & 2(4) + 3(1) + (-1)(2) +  0(7)  \ 
     -7(3) + 2(2) +   1 (-1) + 10(2) & -7(4) + 2(1) +   1 (2) + 10(7)  
  end{bmatrix} 
======  begin{bmatrix}
     13 & 9  \ 
     2 & 102  
  end{bmatrix} 
</math>

<p>As this implies, multiplication is non-commutative in general for matrices, i.e. 
<math>mathbf{AB} ne mathbf{BA}</math> since in this case 
if we reversed the order the resulting matrix <math>mathbf{BA}</math>would be 
4×4 instead of 2×2.</p>

<p>=== More General Approach ===</p>

<p>Now lets visualize A and B as m×n and n×p matrices respectively.</p>

<math>
  mathbf{A} = begin{bmatrix}
     a_{1,1} & a_{1,2} & dots & dots   \ 
     a_{2,1} & a_{2,2} & dots & dots   \
     a_{3,1} & a_{3,2} & ddots & dots  \
     vdots  & vdots  & vdots & a_{m,n}  
  end{bmatrix}
  mathbf{B} = begin{bmatrix}
     b_{1,1} & b_{1,2} & dots & dots   \ 
     b_{2,1} & b_{2,2} & dots & dots   \
     b_{3,1} & b_{3,2} & ddots & dots  \
     vdots  & vdots  & vdots & b_{n,p}  
  end{bmatrix}
</math>

<p>We are going to be adding and multiplying like before, but generally.</p>

<math>
mathbf{AB} = begin{bmatrix}
     a_{1,1}b_{1,1} + a_{1,2}b_{2,1} + dots + a_{1,n}b_{p,1} & dots  \ 
     vdots & a_{m,1}b_{1,1} + a_{m,2}b_{2,p} + dots + a_{m,n}b_{n,p}  
  end{bmatrix} 
</math>

<p>==== Psedocode &amp; General Algorithm ====</p>

<p>So now that we have a general idea of what a matrix is, and how to multiply them
in general, we can derive some psedocode around it.  We could break down the steps
as follows.</p>

<ul>
<li>Check the sizes of two matrices <math>mathbf{A}</math> (m×n) and <math>mathbf{B}</math> (t×u):  if n = t then we can multiply them otherwise no (in that order <math>mathbf{AB}</math>)</li>
<li>If they can be multiplied, then create a new square matrix of size n (or t, since n = t)</li>
<li>For each row in A and each column in <math>mathbf{B}</math> multiply and sum the elements and the place the results in the rows and columns of the result matrix <math>mathbf{AB}</math></li>
</ul>

<p>Here is some psedocode treating matrices like if they have a m element and an n element, so the
dimension of a matrix object is m×n.</p>

<p><code></p>

<p>multiplyMatrix(matrix1, matrix2)</p>

<p>--  Multiplies rows and columns and sums them
  multiplyRowAndColumn(row, column) returns number
  var
    total: number
  begin
    for each rval in row and cval in column
    begin
       total += rval*cval
    end
    return total
  end</p>

<p>begin</p>

<p>--  If the rows don't match up then the function fails</p>

<p>if matrix1:n != matrix2:m  return failure;</p>

<p>dim    = matrix1:n   -- Could also be matrix2:m
  newmat = new squarematrix(dim)  -- Create a new dim x dim matrix
  for each r in matrix1:rows and c in matrix2:columns
  begin</p>

<p>end</p>

<p>end</p>

<p>&lt;\/code></p>

<p>=====  Implementations  =====</p>

<p>====  C#  ====</p>

<p>====  VB  ====</p>

<p>====  Python  ====</p>

<p>====  Ruby  ====</p>

<p>====  Javascript  ====</p>

<p>====  Java  ====</p>

<p>====  Squeak / Smalltalk  ====</p>

<p>====  Scheme / Lisp  ====</p>

<p>====  C  ====</p>

<p>[[http://angelo.freeshell.org/computer/docs/mmult.php|Single Dimension arrays in C]]</p>

<p>[[Category:Algorithms]]</p>