Program to multiply two matrices

Given two matrices, the task to multiply them. Matrices can either be square or rectangular.

Examples:

```Input : mat1[][] = {{1, 2},
{3, 4}}
mat2[][] = {{1, 1},
{1, 1}}
Output : {{3, 3},
{7, 7}}
Input : mat1[][] = {{2, 4},
{3, 4}}
mat2[][] = {{1, 2},
{1, 3}}
Output : {{6, 16},
{7, 18}}
```

Multiplication of Square Matrices :
The below program multiplies two square matrices of size 4*4, we can change N for different dimension.

C++

 `// C++ program to multiply  ` `// two square matrices. ` `#include ` ` `  `using` `namespace` `std; ` ` `  `#define N 4 ` ` `  `// This function multiplies  ` `// mat1[][] and mat2[][], and  ` `// stores the result in res[][] ` `void` `multiply(``int` `mat1[][N],  ` `              ``int` `mat2[][N],  ` `              ``int` `res[][N]) ` `{ ` `    ``int` `i, j, k; ` `    ``for` `(i = 0; i < N; i++) ` `    ``{ ` `        ``for` `(j = 0; j < N; j++) ` `        ``{ ` `            ``res[i][j] = 0; ` `            ``for` `(k = 0; k < N; k++) ` `                ``res[i][j] += mat1[i][k] *  ` `                             ``mat2[k][j]; ` `        ``} ` `    ``} ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `i, j; ` `    ``int` `res[N][N]; ``// To store result ` `    ``int` `mat1[N][N] = {{1, 1, 1, 1}, ` `                      ``{2, 2, 2, 2}, ` `                      ``{3, 3, 3, 3}, ` `                      ``{4, 4, 4, 4}}; ` ` `  `    ``int` `mat2[N][N] = {{1, 1, 1, 1}, ` `                      ``{2, 2, 2, 2}, ` `                      ``{3, 3, 3, 3}, ` `                      ``{4, 4, 4, 4}}; ` ` `  `    ``multiply(mat1, mat2, res); ` ` `  `    ``cout << ````"Result matrix is "````; ` `    ``for` `(i = 0; i < N; i++) ` `    ``{ ` `        ``for` `(j = 0; j < N; j++) ` `        ``cout << res[i][j] << ``" "``; ` `        ``cout << ````" "````; ` `    ``} ` ` `  `    ``return` `0; ` `} ` ` `  `// This code is contributed ` `// by Soumik Mondal `

C

 `// C program to multiply two square matrices. ` `#include ` `#define N 4 ` ` `  `// This function multiplies mat1[][] and mat2[][], ` `// and stores the result in res[][] ` `void` `multiply(``int` `mat1[][N], ``int` `mat2[][N], ``int` `res[][N]) ` `{ ` `    ``int` `i, j, k; ` `    ``for` `(i = 0; i < N; i++) ` `    ``{ ` `        ``for` `(j = 0; j < N; j++) ` `        ``{ ` `            ``res[i][j] = 0; ` `            ``for` `(k = 0; k < N; k++) ` `                ``res[i][j] += mat1[i][k]*mat2[k][j]; ` `        ``} ` `    ``} ` `} ` ` `  `int` `main() ` `{ ` `    ``int` `mat1[N][N] = { {1, 1, 1, 1}, ` `                    ``{2, 2, 2, 2}, ` `                    ``{3, 3, 3, 3}, ` `                    ``{4, 4, 4, 4}}; ` ` `  `    ``int` `mat2[N][N] = { {1, 1, 1, 1}, ` `                    ``{2, 2, 2, 2}, ` `                    ``{3, 3, 3, 3}, ` `                    ``{4, 4, 4, 4}}; ` ` `  `    ``int` `res[N][N]; ``// To store result ` `    ``int` `i, j; ` `    ``multiply(mat1, mat2, res); ` ` `  `    ``printf``(````"Result matrix is "````); ` `    ``for` `(i = 0; i < N; i++) ` `    ``{ ` `        ``for` `(j = 0; j < N; j++) ` `           ``printf``(``"%d "``, res[i][j]); ` `        ``printf``(````" "````); ` `    ``} ` ` `  `    ``return` `0; ` `} `

Java

 `// Java program to multiply two square ` `// matrices. ` `import` `java.io.*; ` ` `  `class` `GFG { ` `     `  ` `  `    ``static` `int` `N = ``4``; ` `     `  `    ``// This function multiplies mat1[][] ` `    ``// and mat2[][], and stores the result ` `    ``// in res[][] ` `    ``static` `void` `multiply(``int` `mat1[][],  ` `                  ``int` `mat2[][], ``int` `res[][]) ` `    ``{ ` `        ``int` `i, j, k; ` `        ``for` `(i = ``0``; i < N; i++) ` `        ``{ ` `            ``for` `(j = ``0``; j < N; j++) ` `            ``{ ` `                ``res[i][j] = ``0``; ` `                ``for` `(k = ``0``; k < N; k++) ` `                    ``res[i][j] += mat1[i][k]  ` `                                ``* mat2[k][j]; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `mat1[][] = { {``1``, ``1``, ``1``, ``1``}, ` `                         ``{``2``, ``2``, ``2``, ``2``}, ` `                         ``{``3``, ``3``, ``3``, ``3``}, ` `                         ``{``4``, ``4``, ``4``, ``4``}}; ` ` `  `        ``int` `mat2[][] = { {``1``, ``1``, ``1``, ``1``}, ` `                         ``{``2``, ``2``, ``2``, ``2``}, ` `                         ``{``3``, ``3``, ``3``, ``3``}, ` `                         ``{``4``, ``4``, ``4``, ``4``}}; ` ` `  `        ``// To store result ` `        ``int` `res[][] = ``new` `int``[N][N] ; ` `        ``int` `i, j; ` `        ``multiply(mat1, mat2, res); ` `     `  `        ``System.out.println(``"Result matrix"` `                                ``+ ``" is "``); ` `        ``for` `(i = ``0``; i < N; i++) ` `        ``{ ` `            ``for` `(j = ``0``; j < N; j++) ` `                ``System.out.print( res[i][j] ` `                                    ``+ ``" "``); ` `            ``System.out.println(); ` `        ``} ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

/div>

Python 3

 `# 4x4 matrix multiplication using Python3 ` `# Function defination ` `def` `matrix_multiplication(M,N): ` `    ``# List to store matrix multiplication result ` `    ``R ``=` `[[``0``, ``0``, ``0``, ``0``],  ` `        ``[``0``, ``0``, ``0``, ``0``],  ` `        ``[``0``, ``0``, ``0``, ``0``], ` `        ``[``0``, ``0``, ``0``, ``0``]]  ` ` `  `    ``for` `i ``in` `range``(``0``, ``4``):  ` `        ``for` `j ``in` `range``(``0``, ``4``): ` `            ``for` `k ``in` `range``(``0``, ``4``):  ` `                ``R[i][j] ``+``=` `M[i][k] ``*` `N[k][j]  ` ` `  `    ``for` `i ``in` `range``(``0``,``4``):  ` `        ``for` `j ``in` `range``(``0``,``4``):  ` `            ``#if we use print(), by default cursor moves to next line each time,  ` `            ``#Now we can explicitly define ending character or secuence passing ` `            ``#second parameter as end="" ` `            ``#syntax: print(, end="") ` `            ``#Here space (" ") is used to print a gape after printing  ` `            ``#each element of R ` `            ``print``(R[i][j],end``=``" "``) ` `        ``print``(````" "````,end``=``"") ` ` `  `# First matrix. M is a list ` `M ``=` `[[``1``, ``1``, ``1``, ``1``],  ` `    ``[``2``, ``2``, ``2``, ``2``],  ` `    ``[``3``, ``3``, ``3``, ``3``], ` `    ``[``4``, ``4``, ``4``, ``4``]] ` ` `  `# Second matrix. N is a list ` `N ``=` `[[``1``, ``1``, ``1``, ``1``],  ` `    ``[``2``, ``2``, ``2``, ``2``],  ` `    ``[``3``, ``3``, ``3``, ``3``], ` `    ``[``4``, ``4``, ``4``, ``4``]]  ` `     `  `# Call matrix_multiplication function ` `matrix_multiplication(M,N) ` ` `  `# This code is contributed by Santanu `

C#

 `// C# program to multiply two square ` `// matrices. ` `using` `System; ` ` `  `class` `GFG { ` `     `  ` `  `    ``static` `int` `N = 4; ` `     `  `    ``// This function multiplies mat1[][] ` `    ``// and mat2[][], and stores the result ` `    ``// in res[][] ` `    ``static` `void` `multiply(``int``[,] mat1,  ` `                ``int` `[,]mat2, ``int` `[,]res) ` `    ``{ ` `        ``int` `i, j, k; ` `        ``for` `(i = 0; i < N; i++) ` `        ``{ ` `            ``for` `(j = 0; j < N; j++) ` `            ``{ ` `                ``res[i,j] = 0; ` `                ``for` `(k = 0; k < N; k++) ` `                    ``res[i,j] += mat1[i,k]  ` `                                ``* mat2[k,j]; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `[,]mat1 = { {1, 1, 1, 1}, ` `                        ``{2, 2, 2, 2}, ` `                        ``{3, 3, 3, 3}, ` `                        ``{4, 4, 4, 4}}; ` ` `  `        ``int` `[,]mat2 = { {1, 1, 1, 1}, ` `                        ``{2, 2, 2, 2}, ` `                        ``{3, 3, 3, 3}, ` `                        ``{4, 4, 4, 4}}; ` ` `  `        ``// To store result ` `        ``int` `[,]res = ``new` `int``[N,N] ; ` `        ``int` `i, j; ` `        ``multiply(mat1, mat2, res); ` `     `  `        ``Console.WriteLine(``"Result matrix"` `                                ``+ ``" is "``); ` `        ``for` `(i = 0; i < N; i++) ` `        ``{ ` `            ``for` `(j = 0; j < N; j++) ` `                ``Console.Write( res[i,j] ` `                                    ``+ ``" "``); ` `            ``Console.WriteLine(); ` `        ``} ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

PHP

 ` `

Output:

```Result matrix is
10 10 10 10
20 20 20 20
30 30 30 30
40 40 40 40 ```

Multiplication of Rectangular Matrices :
We use pointers in C to multiply to matrices. Please refer the following post as a prerequisite of the code.

C++

 `// C++ program to multiply two ` `// rectangular matrices ` `#include ` `using` `namespace` `std; ` ` `  `// Multiplies two matrices mat1[][]  ` `// and mat2[][] and prints result. ` `// (m1) x (m2) and (n1) x (n2) are  ` `// dimensions of given matrices. ` `void` `multiply(``int` `m1, ``int` `m2, ``int` `mat1[][2],  ` `              ``int` `n1, ``int` `n2, ``int` `mat2[][2]) ` `{ ` `    ``int` `x, i, j; ` `    ``int` `res[m1][n2]; ` `    ``for` `(i = 0; i < m1; i++)  ` `    ``{ ` `        ``for` `(j = 0; j < n2; j++)  ` `        ``{ ` `            ``res[i][j] = 0; ` `            ``for` `(x = 0; x < m2; x++)  ` `            ``{ ` `                ``*(*(res + i) + j) += *(*(mat1 + i) + x) * ` `                                     ``*(*(mat2 + x) + j); ` `            ``} ` `        ``} ` `    ``} ` `    ``for` `(i = 0; i < m1; i++)  ` `    ``{ ` `        ``for` `(j = 0; j < n2; j++)  ` `        ``{ ` `            ``cout << *(*(res + i) + j) << ``" "``; ` `        ``} ` `        ``cout << ````" "````; ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `mat1[][2] = { { 2, 4 }, { 3, 4 } }; ` `    ``int` `mat2[][2] = { { 1, 2 }, { 1, 3 } }; ` `    ``int` `m1 = 2, m2 = 2, n1 = 2, n2 = 2; ` `    ``multiply(m1, m2, mat1, n1, n2, mat2); ` `    ``return` `0; ` `} ` ` `  `// This code is contributed  ` `// by Akanksha Rai(Abby_akku) `

C

 `// C program to multiply two rectangular matrices ` `#include ` ` `  `// Multiplies two matrices mat1[][] and mat2[][] ` `// and prints result. ` `// (m1) x (m2) and (n1) x (n2) are dimensions ` `// of given matrices. ` `void` `multiply(``int` `m1, ``int` `m2, ``int` `mat1[][m2], ` `            ``int` `n1, ``int` `n2, ``int` `mat2[][n2]) ` `{ ` `    ``int` `x, i, j; ` `    ``int` `res[m1][n2]; ` `    ``for` `(i = 0; i < m1; i++) ` `    ``{ ` `        ``for` `(j = 0; j < n2; j++) ` `        ``{ ` `            ``res[i][j] = 0; ` `            ``for` `(x = 0; x < m2; x++) ` `            ``{ ` `                ``*(*(res + i) + j) += *(*(mat1 + i) + x) * ` `                                    ``*(*(mat2 + x) + j); ` `            ``} ` `        ``} ` `    ``} ` `    ``for` `(i = 0; i < m1; i++) ` `    ``{ ` `        ``for` `(j = 0; j < n2; j++) ` `        ``{ ` `            ``printf``(``"%d "``, *(*(res + i) + j)); ` `        ``} ` `        ``printf``(````" "````); ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `mat1[][2] = { { 2, 4 }, { 3, 4 } }; ` `    ``int` `mat2[][2] = { { 1, 2 }, { 1, 3 } }; ` `    ``int` `m1 = 2, m2 = 2, n1 = 2, n2 = 2; ` `    ``multiply(m1, m2, mat1, n1, n2, mat2); ` `    ``return` `0; ` `} `

PHP

Output:

```6 16
7 18
```

The time complexity of the above program is O(n3). It can be optimized using Strassen’s Matrix Multiplication