Wikia

Programmer's Wiki

Matrix multiplication

Talk2
398pages on
this wiki

Introduction Edit

Prerequisites Edit

It is assumed that those reading this have a basic understanding of what a matrix is and 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.

If you need some background Go here

Matrix Multiplication Basics Edit

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 \in \mathbb{N}}. The resulting matrix will be of dimension m×p.

Example: 2x4 Multiplied by 4x2 Edit

Take a matrix 2x4 call it \mathbf{A}; another of dimension 4x2 and call it \mathbf{B}. Give them some arbitrary values and let's do some multiplication.


 \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}

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.

To make a long story short, our matrix would be:


\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 & 46  
  \end{bmatrix}

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

More General ApproachEdit

Now let's visualize A and B as m×n and n×p matrices respectively.


  \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}

We are going to be adding and multiplying like before, but generally.


\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}

General AlgorithmsEdit

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

  1. Check the sizes of two matrices \mathbf{A} (m×n) and \mathbf{B} (t×u): if n = t then we can multiply them otherwise no (in that order \mathbf{AB})
  2. If they can be multiplied, then create a new matrix of size m by u
  3. For each row in A and each column in \mathbf{B} multiply and sum the elements and the place the results in the rows and columns of the result matrix \mathbf{AB}

PseudocodeEdit

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

multiplyMatrix(matrix1, matrix2)

-- 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

begin

-- If the rows don't match up then the function fails

  if matrix1:n != matrix2:m  return failure;

  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
    
  end
end

Implementations Edit

C Sharp Edit

// Program in C# to multiply two matrices using Rectangular arrays.
using System;
class MatrixMultiplication
{
	int[,] a;
	int[,] b;
	int[,] c;
	
	public void ReadMatrix()
	{
		Console.WriteLine("\n Size of Matrix 1:");
		Console.Write("\n Enter the number of rows in Matrix 1 :");
		int m=int.Parse(Console.ReadLine());
		Console.Write("\n Enter the number of columns in Matrix 1 :");
		int n=int.Parse(Console.ReadLine());
		a=new int[m,n];
		Console.WriteLine("\n Enter the elements of Matrix 1:");
		for(int i=0;i<a.GetLength(0);i++)
		{
			for(int j=0;j<a.GetLength(1);j++)
			{
				a[i,j]=int.Parse(Console.ReadLine());
			}
		}
		
		Console.WriteLine("\n Size of Matrix 2 :");
		Console.Write("\n Enter the number of rows in Matrix 2 :");
		m=int.Parse(Console.ReadLine());
		Console.Write("\n Enter the number of columns in Matrix 2 :");
		n=int.Parse(Console.ReadLine());
		b=new int[m,n];
		Console.WriteLine("\n Enter the elements of Matrix 2:");
		for(int i=0;i<b.GetLength(0);i++)
		{
			for(int j=0;j<b.GetLength(1);j++)
			{
				b[i,j]=int.Parse(Console.ReadLine());
			}
		}
	}
	
	public void PrintMatrix()
	{
		Console.WriteLine("\n Matrix 1:");
		for(int i=0;i<a.GetLength(0);i++)
		{
			for(int j=0;j<a.GetLength(1);j++)
			{
				Console.Write("\t"+a[i,j]);
			}
			Console.WriteLine();
		}
		Console.WriteLine("\n Matrix 2:");
		for(int i=0;i<b.GetLength(0);i++)
		{
			for(int j=0;j<b.GetLength(1);j++)
			{
				Console.Write("\t"+b[i,j]);
			}
			Console.WriteLine();
		}
		Console.WriteLine("\n Resultant Matrix after multiplying Matrix 1 & Matrix 2:");
		for(int i=0;i<c.GetLength(0);i++)
		{
			for(int j=0;j<c.GetLength(1);j++)
			{
				Console.Write("\t"+c[i,j]);
			}
			Console.WriteLine();
		}
		
	}
	public void MultiplyMatrix()
	{
		if(a.GetLength(1)==b.GetLength(0))
		{
			c=new int[a.GetLength(0),b.GetLength(1)];
			for(int i=0;i<c.GetLength(0);i++)
			{
				for(int j=0;j<c.GetLength(1);j++)
				{
					c[i,j]=0;
					for(int k=0;k<a.GetLength(1);k++) // OR k<b.GetLength(0)
					c[i,j]=c[i,j]+a[i,k]*b[k,j];
				}
			}
		}
		else
		{
			Console.WriteLine("\n Number of columns in Matrix1 is not equal to Number of rows in Matrix2.");
			Console.WriteLine("\n Therefore Multiplication of Matrix1 with Matrix2 is not possible");
			Environment.Exit(-1);
		}
	}
}
class Matrices
{
	public static void Main()
	{
		MatrixMultiplication MM=new MatrixMultiplication();
		MM.ReadMatrix();
		MM.MultiplyMatrix();
		MM.PrintMatrix();
	}
}

VB.NET Edit

Public Module MatrixMultiplication

    ' Generic stand-alone method
    ' Uses LINQ.
    Public Function Multiply(matrix1 As IEnumerable(Of IEnumerable(Of Double)), _
                             matrix2 As IEnumerable(Of IEnumerable(Of Double))
                    As IEnumerable(Of IEnumerable(Of Double))
        If matrix1.Count = matrix2(0).Count Then
            Dim ret(matrix1(0).Count, matrix2.Count) As Double
            For i As Integer = 0 To ret.Count - 1
                For j As Integer = 0 To ret(0).Count - 1
                    ret(i, j) = 0
                    For k As Integer = 0 To matrix1(0).Count - 1
                        ret(i, j) = ret(i, j) + a(i, k) + b(k, j)
                    Next
                Next
            Next
        Else
             New RankException("Number of columns in matrix1 is not equal to the number of rows in matrix2.")
        End If
    End Function

    ' This method can be run in a console app.
    Public Sub Main()
        Dim m_1 As Integer, n_1 As Integer, m_2 As Integer, n_2 As Integer
        Try
            Console.WriteLine("Size of matrix 1:")
            Console.Write("Number of rows: ")
            m_1 = Integer.Parse(Console.ReadLine())
            Console.Write("Number of columns: ")
            n_1 = Integer.Parse(Console.ReadLine())
            Dim matrix1(m_1, n_1) As Double

            Console.WriteLine("Enter the elements of matrix 1:")
            For i As Integer = 0 To m_1 - 1
                For j As Integer = 0 To n_1 - 1
                    Console.Write("Element at " & i & ", " & j)
                    matrix1(i, j) = Integer.Parse(Console.ReadLine())
                Next
            Next
            
            Console.WriteLine("Size of matrix 2:")
            Console.Write("Number of rows: ")
            m_2 = Integer.Parse(Console.ReadLine())
            Console.Write("Number of columns: ")
            n_2 = Integer.Parse(Console.ReadLine())

            Console.WriteLine("Enter the elements of matrix 2:")
            For i As Integer = 0 To m_2 - 1
                For j As Integer = 0 To n_2 - 1
                    Console.Write("Element at " & i & ", " & j)
                    matrix2(i, j) = Integer.Parse(Console.ReadLine())
                Next
            Next

            Dim product(,) As Double = Multiply(matrix1, matrix2)

            Console.WriteLine("The product of the two matrices is:")
            For i As Integer = 0 To product.Count - 1
                For j As Integer = 0 To product(0).Count - 1
                    Console.Write(product(i, j) & " ")
                Next
                Console.WriteLine()
            Next
        Catch ex As Exception
            Console.WriteLine("An error occured. The message associated with the error was:")
            Console.WriteLine(ex.Message)
        End Try

        Console.WriteLine()
        Console.WriteLine("Press any key to exit.")
        Console.ReadKey()
    End Sub
End Module

Python Edit

def multmat(a,b):
	m=len(a)
	n=len(a[0])
	k=len(b)
	res=[]
	if len(b) != 1:
		p=len(b[0])-1
	else:
		p=0
	if len(b)==0:
		print('bad size')
	elif n!=k:
		print('bad size')
	else:
		#print('good size')
		n=k
		#print('k=',k,'n=',n)
		for q in range(m):
			res.append([0])
			#print('res=',res)
		for q in range(m):
			for w in range(p):
				res[q].append(0)
		for i in range(m):


			for j in range(p+1):


				for r in range(n):
					#print('ijr:res',i,j,r,res)

					res[i][j] =a[i][r]*b[r][j]+res[i][j]
	return res


+----------------+
| AN ALTERNATIVE |
+----------------+

...
s = 0
for i in range(self.rows):
    for c in range(other.cols):
        s = 0
        for j in range(other.rows):
            s += self.mat[i][j] * other.mat[j][c]
                    
        sum.mat[i][c] = s
...

Ruby Edit

 require 'matrix'
 
 def read_matrix
   puts "Enter number of column for matrix: "
   _cols = gets.chomp!.to_i
   
   puts "Enter number of rows for matrix: "
   _rows = gets.chomp!.to_i
   
   raise "Invalid sizes" unless _rows.is_a? Fixnum && _cols.is_a? Fixnum
   
   puts "Enter the elements of the matrix (one per line)"
   a = Matrix.build _rows, _cols, do |m|
     m = gets.chomp!.to_i
   end
   
   raise "An element is not a number" if a.any? { |eL| !eL.is_a? Fixnum }
   
   a
 end
 
 puts "reading first matrix..."
 mat1 = read_matrix
 puts "reading second matrix..."
 mat2 = read_matrix
 
 begin
   puts mat1 * mat2
 rescue ExceptionForMatrix::ErrDimensionMismatch => e
   puts e.message
 end
 
 
 
   # or if we don't care about user input
   # following the C++ example ..to show you how concise Ruby is
   
   Matrix.build(4) { rand } * Matrix.build(4) { rand }

JavaEdit

public class SimpleMatrix  {

	private Double data[][];

	private Boolean transposed = false;
	
	public SimpleMatrix(int i, int j) {
		data = new Double[i][j];
		
	}
	
	

	
	public SimpleMatrix product(SimpleMatrix m) {
		if(this.getColumns() != m.getRows()) return null;
		SimpleMatrix outcome = new SimpleMatrix(this.getRows(),m.getColumns());
		Double sumProduct = 0.0;
	
		for(int i = 0 ; i < getRows(); i++)
		{
			for(int j = 0; j < m.getColumns(); j++)
			{
				sumProduct=0.0;
				
				for(int k=0;k<getColumns();k++)
				{
					sumProduct+=this.get(i, k)*m.get(k,j);	
				}//end k
				
				outcome.set(i, j, sumProduct);
				
			}//end j
		}//end i
		
		return outcome;
	}

        @Override
	protected Object clone() throws CloneNotSupportedException {
		SimpleMatrix m = new SimpleMatrix(this.getRows(),this.getColumns());
		m.transposed = this.transposed;
		m.vectorSpace = this.vectorSpace;
		
		
		for(int i = 0 ; i < getRows(); i++)
		{
			for(int j = 0; j < getColumns(); j++)
			{
				m.set(i, j, this.get(i, j));
			}
		
		}
		
		
		return m;
	}

	
	public void transpose()
	{
		transposed = !transposed;
	}
	
	public Boolean isTransposed()
	{
		return transposed;
	}
	

	
	public int getRows() {
		return transposed?data[0].length : data.length;
	}

	
	public int getColumns() {
		
		return transposed? data.length : data[0].length;
	}

	
	public void set(int i, int j, Double t) {
		data[i][j] = t;
		
	}

	
	public Double get(int i, int j) {
		
		return isTransposed()?data[j][i]:data[i][j];
	}
	
	@Override
	public String toString() {
		StringBuffer outcome = new StringBuffer();
		outcome.append("{[");
		for(int i = 0 ; i < getRows(); i++)
		{
			for(int j = 0; j < getColumns(); j++)
			{
				outcome.append(get(i,j)).append(",");
			}
			outcome.deleteCharAt(outcome.length()-1).append("]\n[");
		}
		outcome.deleteCharAt(outcome.length()-1).deleteCharAt(outcome.length()-1).append("}");
		
		
		
		return outcome.toString();
	}
	
	
	
	
	public static void main(String[] args) throws CloneNotSupportedException{
		
		SimpleMatrix m = new SimpleMatrix(2,3);
		m.set(0,0,1.0);
		m.set(0,1,2.0);	
		m.set(0,2,3.0);	
		m.set(1,0,4.0);	
		m.set(1,1,5.0);	
		m.set(1,2,6.0);	
		
		
		System.out.println("Original:\n"+m);
		
		
		SimpleMatrix m2 = (SimpleMatrix) m.clone();
		m2.transpose();
		System.out.println("Transpose:\n"+m2);
		
		Matrix m3 = m.product(m2);
		System.out.println("Product: \n"+m3);
		
	
		
	}
	
	

}


C++ Edit

 int main(void) 
 {
	const int ROW=4, COL=4, INNER=4;
	int A[ROW][INNER], int B[INNER][COL], int C[ROW][COL];
	for (int row = 0; row != ROW; ++row) 
	{
 		for (int col = 0; col != COL; ++col)
		{
			int sum = 0;
			for (int inner = 0; inner != INNER; ++inner)
			{
				sum += A[row][inner] * B[inner][col];
			}
			C[row][col] = sum;
		}
	}
	return 0;
 }

Around Wikia's network

Random Wiki