Matrix Operations in Go (Part 1)
oli wursterJust for curiosity, I want to program a library for matrix operations in Go. I'm aware, that there are ready-to-use libraries available already, such as:
are there more? I'm sure there are more.
Anyways, let's see if we can do that...
Questions
What do we need for this? What do we already know? The last time I got in touch with matrix operations in school is already a few years ago. If I think about it it's already more than two decades ago... I feel old now. Anyways, here's what we need to find out:
What are matrices?
What (mathematical) operations exist on matrices?
Which operation to implement first?
What are matrices?
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. A matrix is usually denoted by a capital letter, such as A, and its entries are denoted by lower-case letters with subscripts, such as a_ij.
A matrix with m rows and n columns is called an m x n matrix. The order or size of a matrix is written as m x n.
Here is an example of a 3 x 4 matrix:
[ 1 2 3 4 ]
[ 5 6 7 8 ]
[ 9 10 11 12 ]
In this matrix, the first row contains the entries 1, 2, 3, and 4, the second row contains the entries 5, 6, 7, and 8, and the third row contains the entries 9, 10, 11, and 12.
Matrices are used to represent and manipulate data in many areas of mathematics, science, and engineering. They have applications in linear algebra, calculus, statistics, optimization, and many other fields.
Matrices can be added, subtracted, and multiplied by scalars and other matrices. Matrix multiplication is an important operation in linear algebra and is used in many applications.
What operations exist on matrices?
Addition
Subtraction
Multiplication
with scalars
with other matrices
Matrix addition
Matrix addition is a mathematical operation that takes two matrices of the same size and produces a new matrix of the same size. The addition is performed element-wise, which means that corresponding entries in the two matrices are added together.
Given two matrices A and B of the same size, denoted as A = [a_ij] and B = [b_ij], the sum of A and B, denoted as A + B, is a matrix of the same size as A and B, and is defined as follows:
(A + B) = [a_ij + b_ij]
That is, each entry in the resulting matrix is obtained by adding the corresponding entries in the two matrices.
Here's an example to illustrate how matrix addition works. Consider the following matrices:
A = [1 2 3]
[4 5 6]
B = [7 8 9]
[10 11 12]
To add A and B, we first identify that A and B are both 2 x 3 matrices of the same size. Therefore, we can add them element-wise to obtain the sum A + B:
A + B = [1 + 7 2 + 8 3 + 9]
[4 + 10 5 + 11 6 + 12]
= [8 10 12]
[14 16 18]
Therefore, the sum of A and B is:
A + B = [8 10 12]
[14 16 18]
Matrix addition is an important operation in linear algebra and is used in many applications, including solving systems of equations, representing and manipulating data, and in numerical analysis.
Matrix subtraction
Matrix subtraction is a mathematical operation that takes two matrices of the same size and produces a new matrix of the same size. The subtraction is performed element-wise, which means that corresponding entries in the two matrices are subtracted from each other.
Given two matrices A and B of the same size, denoted as A = [a_ij] and B = [b_ij], the difference of A and B, denoted as A - B, is a matrix of the same size as A and B, and is defined as follows:
(A - B) = [a_ij - b_ij]
That is, each entry in the resulting matrix is obtained by subtracting the corresponding entries in the two matrices.
Here's an example to illustrate how matrix subtraction works. Consider the following matrices:
A = [1 2 3]
[4 5 6]
B = [7 8 9]
[10 11 12]
To subtract B from A, we first identify that A and B are both 2 x 3 matrices of the same size. Therefore, we can subtract them element-wise to obtain the difference A - B:
A - B = [1 - 7 2 - 8 3 - 9]
[4 - 10 5 - 11 6 - 12]
= [-6 -6 -6]
[-6 -6 -6]
Therefore, the difference of A and B is:
A - B = [-6 -6 -6]
[-6 -6 -6]
Matrix subtraction is an important operation in linear algebra and is used in many applications, including solving systems of equations, representing and manipulating data, and in numerical analysis.
Matrix multiplication with a scalar
Matrix multiplication with a scalar is a mathematical operation that takes a matrix and a scalar and produces a new matrix of the same size as the original matrix. The scalar multiplication is performed element-wise, which means that each entry in the matrix is multiplied by the scalar.
Given a matrix A of size m x n and a scalar c, the scalar product of A and c, denoted as cA, is a matrix of the same size as A, and is defined as follows:
(cA) = [ca_ij]
That is, each entry in the resulting matrix is obtained by multiplying the corresponding entry in A by scalar c.
Here's an example to illustrate how matrix multiplication with a scalar works. Consider the following matrix:
A = [1 2 3]
[4 5 6]
To multiply A by the scalar 2, we multiply each entry in A by 2 to obtain the product 2A:
2A = [2*1 2*2 2*3]
[2*4 2*5 2*6]
= [2 4 6]
[8 10 12]
Therefore, the product of A and 2 is:
2A = [2 4 6]
[8 10 12]
Matrix multiplication with a scalar is an important operation in linear algebra and is used in many applications, including scaling and transforming matrices, numerical analysis, and in many other areas of mathematics and engineering.
Matrix multiplication with another matrix
Matrix multiplication is a mathematical operation that takes two matrices and produces a new matrix. In order for matrix multiplication to be defined, the number of columns in the first matrix must be equal to the number of rows in the second matrix.
To multiply two matrices A and B, we first identify the dimensions of the matrices. If A is an m x n matrix (m rows and n columns) and B is an n x p matrix (n rows and p columns), then the product of A and B, denoted AB, is an m x p matrix.
The entries of the product matrix AB are given by the dot product of the corresponding row of matrix A and the corresponding column of matrix B. Specifically, if C = AB, then the (i,j)-entry of C is given by:
C(i,j) = sum(A(i,k) * B(k,j), k=1 to n)
where A(i,k) is the (i,k)-entry of matrix A and B(k,j) is the (k,j)-entry of matrix B.
Here's an example to illustrate how matrix multiplication works. Let A be the following 2 x 3 matrix:
A = [1 2 3]
[4 5 6]
Let B be the following 3 x 2 matrix:
B = [7 8]
[9 10]
[11 12]
To compute AB, we first identify that A has 2 rows and 3 columns, while B has 3 rows and 2 columns. Therefore, we can multiply AB, and the resulting matrix will have 2 rows and 2 columns.
The (1,1)-entry of AB is given by:
C(1,1) = A(1,1) * B(1,1) + A(1,2) * B(2,1) + A(1,3) * B(3,1)
= 1 * 7 + 2 * 9 + 3 * 11
= 58
Similarly, we can compute the other entries of AB:
C(1,2) = A(1,1) * B(1,2) + A(1,2) * B(2,2) + A(1,3) * B(3,2)
= 1 * 8 + 2 * 10 + 3 * 12
= 64
C(2,1) = A(2,1) * B(1,1) + A(2,2) * B(2,1) + A(2,3) * B(3,1)
= 4 * 7 + 5 * 9 + 6 * 11
= 139
C(2,2) = A(2,1) * B(1,2) + A(2,2) * B(2,2) + A(2,3) * B(3,2)
= 4 * 8 + 5 * 10 + 6 * 12
= 154
Therefore, the product of A and B is:
AB = [58 64]
[139 154]
This is how matrix multiplication works. It is an important operation in linear algebra and is used in many areas of science and engineering.
What to implement first?
Let's start with the simplest operation(s) addition and subtraction. The rules are clear. Both matrices must be of the same size.
Here's a simple function in Go that adds two matrices:
func addMatrices(a [][]int, b [][]int) [][]int {
m := len(a)
n := len(a[0])
c := make([][]int, m)
for i := 0; i < m; i++ {
c[i] = make([]int, n)
for j := 0; j < n; j++ {
c[i][j] = a[i][j] + b[i][j]
}
}
return c
}
Subtraction should be just as simple:
func subtractMatrices(a [][]int, b [][]int) [][]int {
m := len(a)
n := len(a[0])
c := make([][]int, m)
for i := 0; i < m; i++ {
c[i] = make([]int, n)
for j := 0; j < n; j++ {
c[i][j] = a[i][j] - b[i][j]
}
}
return c
}
As you can imagine, the only difference is the operator between a[i][j] - b[i][j] in the loop.
The scalar multiplication is also straight forward:
func scalarMultiply(a [][]int, c int) [][]int {
m := len(a)
n := len(a[0])
b := make([][]int, m)
for i := 0; i < m; i++ {
b[i] = make([]int, n)
for j := 0; j < n; j++ {
b[i][j] = a[i][j] * c
}
}
return b
}
Now to the matrix multiplication with another matrix:
func multiplyMatrices(a [][]int, b [][]int) [][]int {
m := len(a)
n := len(b[0])
p := len(b)
c := make([][]int, m)
for i := 0; i < m; i++ {
c[i] = make([]int, n)
for j := 0; j < n; j++ {
for k := 0; k < p; k++ {
c[i][j] += a[i][k] * b[k][j]
}
}
}
return c
}
Test the stuff
import (
"testing"
)
func TestMultiplyMatrices(t *testing.T) {
a := [][]int{{1, 2, 3}, {4, 5, 6}}
b := [][]int{{7, 8}, {9, 10}, {11, 12}}
expected := [][]int{{58, 64}, {139, 154}}
// Verify functionality
c := multiplyMatrices(a, b)
if !matrixEqual(c, expected) {
t.Errorf("multiplyMatrices(%v, %v) = %v, expected %v", a, b, c, expected)
}
// Benchmark performance
for i := 0; i < 1000000; i++ {
multiplyMatrices(a, b)
}
}
// Utility function to compare two matrices for equality
func matrixEqual(a [][]int, b [][]int) bool {
if len(a) != len(b) || len(a[0]) != len(b[0]) {
return false
}
for i := 0; i < len(a); i++ {
for j := 0; j < len(a[0]); j++ {
if a[i][j] != b[i][j] {
return false
}
}
}
return true
}
Conclusion
In theory, matrix operations are simple. But they are computationally expensive. A loop in a loop in a loop for matrix multiplications with other matrices sounds expensive already. I guess that's the reason why everyone tries to offload matrix operations to specialized hardware, like graphics cards.
Have fun, cheers!
Subscribe to my newsletter
Read articles from oli wurster directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by