Skip to main content

Discrete Mathematics for Computing (Draft)

Christine Caples, Adam Gilbert, Melanie Fraser

Section 7.2 Two-Dimensional Arrays (Matrices)

We ended our last section by mentioning the outer-product between two arrays. Unlike the inner-product, the outer-product is defined even between arrays whose lengths do not match. Before we return to the definition of the outer-product, let’s take a look at two-dimensional arrays, which are often referred to as matrices.

Subsection 7.2.1 What is a two-dimensional array?

A matrix is a two-dimensional array. That is, a matrix is an array which has both rows and columns. An example of a two-by-three matrix appears below.
\begin{align*} \left[\begin{array}{ccc} 2 \amp 4 \amp -11\\ -7 \amp \frac{3}{4} \amp \frac{5}{2}\end{array}\right] \end{align*}
Seeing the form of a general \(m\times n\) (\(m\) by \(n\)) matrix gives a bit of insight as to how matrix elements are organized and how they can be accessed in a computing environment. An \(m\times n\) matrix is a two-dimensional array with \(m\) rows and \(n\) columns. The general from of an \(m\times n\) matrix appears below.
\begin{align*} \left[\begin{array}{cccc} a_{11} \amp a_{12} \amp \cdots \amp a_{1n}\\ a_{21} \amp a_{22} \amp \cdots \amp a_{2n}\\ \vdots \amp \amp \ddots \amp \vdots\\ a_{m1} \amp a_{m2} \amp \cdots \amp a_{mn}\end{array}\right] \end{align*}
From the definition above, we can see that the element \(a_{ij}\) occupies the position in row \(i\) and column \(j\text{.}\) This insight allows us to access matrix elements through code. The following example of an algorithm to convert a list to a matrix shows how accessing elements of a two-dimensional array can be done.
def list_to_matrix(myList, rows):
  list_length = length(myList)
  if (rows does not divide list_length):
    print("Warning: number of rows must divide the length of the list")
    return NULL

  columns = list_length / rows 
  myMatrix = a rows x columns array
  list_counter = 0

  for row in [0, 1, ..., rows - 1]:
    for column in [0, 1, ..., columns - 1]:
      myMatrix[row, column] = myList[list_counter]
      list_counter = list_counter + 1

  return myMatrix
Notice the use of the nested for loops to move throw the row and column combinations. Complete the exercise below to determine the run-time complexity of the list_to_matrix() algorithm proposed above.

Checkpoint 7.2.1. List to Matrix Complexity.

Subsection 7.2.2 Matrix Addition/Subtraction

Now that we know how matrices are constructed, we can think about operations with these two-dimensional structures. Just like with one-dimensional arrays, matrix addition and subtraction is done element-wise. This requires that two matrices have the same dimensions (the same number of rows and same number of columns) as one another in order to add or subtract the two objects. An algorithm to define matrix addition appears below.
def matrix_sum(myMatrix1, myMatrix2):
  rows_matrix1 = number of rows in myMatrix1
  rows_matrix2 = number of rows in muMatrix2
  cols_matrix1 = number of columns in myMatrix1
  cols_matrix2 = number of columns in muMatrix2
  if (rows_matrix1 not equal to rows_matrix2) or (cols_matrix1 not equal to cols_matrix2):
    print("Warning: matrix dimensions don't match")
    return NULL

  sumMatrix = a rows_matrix1 x cols_matrix1 array

  for row in [0, 1, ..., rows_matrix1 - 1]:
    for column in [0, 1, ..., cols_matrix1 - 1]:
      sumMatrix[row, column] = myMatrix1[row, column] + myMatrix2[row, column]

  return sumMatrix
Complete the exercise below to determine the run-time complexity of the matrix_sum() algorithm outlined here.

Checkpoint 7.2.2. Matrix Sum Complexity.

Try the following exercises to test your understanding of computing matrix sums and differences.

Checkpoint 7.2.3. Sum of \(2\times 2\) Matrices.

Checkpoint 7.2.4. Sum/Difference of \(m\times n\) Matrices 1.

Checkpoint 7.2.5. Sum/Difference of \(m\times n\) Matrices 2.

Checkpoint 7.2.6. Sum/Difference of \(m\times n\) Matrices 3.

Checkpoint 7.2.7. Sum/Difference of \(m\times n\) Matrices 4.

Subsection 7.2.3 Scalar Multiplication

Again, similar to one-dimensional arrays, scalar multiplication with matrices is done element-wise. The algorithm below describes a method for computing a scalar multiple of an \(m\times n\) matrix.
def scalar_mult_matrix(myScalar, myMatrix):
  rows = number of rows in myMatrix
  cols = number of columns in myMatrix
  scaled_matrix = a rows x cols array

  for row in [0, 1, ..., rows - 1]:
    for col in [0, 1, ..., cols - 1]:
      scaled_matrix[row, col] = myScalar * myMatrix[row, col]

  return scaled_matrix
Complete the exercise below to determine the run-time complexity of the scalar_mult_matrix() algorithm outlined above.

Checkpoint 7.2.8. Scalar Multiplication Complexity.

Try the following exercises to test your understanding of computing scalar multiples of matrices.

Checkpoint 7.2.9. Scalar Multiplication 1.

Checkpoint 7.2.10. Scalar Multiplication 2.

Checkpoint 7.2.11. Scalar Multiplication 3.

Checkpoint 7.2.12. Scalar Multiplication 4.

Subsection 7.2.4 Matrix Multiplication

The operation of matrix multiplication is more complex that simply multiplying element-wise. Given two matrices \(A\) and \(B\text{,}\) we compute the \(ij^{\text{th}}\) entry of the matrix product \(AB\) by taking the inner product between the \(i^{\text{th}}\) row of the matrix \(A\) with the \(j^{\text{th}}\) column of the matrix \(B\text{.}\) This forces that the number of columns in \(A\) matches the number of rows in \(B\text{.}\) The resulting matrix \(AB\) then has a number of rows equal to the number of rows in \(A\) and a number of columns equal to the number of columns in \(B\text{.}\)
Below is an example showing how to compute the matrix product between a \(2\times 2\) matrix and a \(2\times 3\) matrix.

Example 7.2.13. Matrix Product.

Compute the matrix product \(AB\text{,}\) where \(A = \left[\begin{array}{cc} 1 \amp 2\\ 0 \amp -3\end{array}\right]\) and \(B = \left[\begin{array}{ccc} 5 \amp -4 \amp -2\\ 1 \amp -1 \amp 3\end{array}\right]\text{.}\)
Solution.
\begin{align*} AB \amp = \left[\begin{array}{cc} 1 \amp 2\\ 0 \amp -3\end{array}\right]\cdot \left[\begin{array}{ccc} 5 \amp -4 \amp -2\\ 1 \amp -1 \amp 3\end{array}\right]\\ \amp = \left[\begin{array}{ccc} \left(\left(1\cdot 5\right) + \left(2\cdot 1\right)\right) \amp \left(\left(1\cdot \left(-4\right)\right) + \left(2\cdot\left(-1\right)\right)\right) \amp \left(\left(1\cdot \left(-2\right)\right) + \left(2\cdot 3\right)\right)\\ \left(\left(0\cdot 5\right) + \left(-3\cdot 1\right)\right) \amp \left(\left(0\cdot \left(-4\right)\right) + \left(-3\cdot\left(-1\right)\right)\right) \amp \left(\left(0\cdot \left(-2\right)\right) + \left(-3\cdot 3\right)\right)\end{array}\right]\\ \amp = \left[\begin{array}{ccc} \left(5 + 2\right) \amp \left(-4 -2\right) \amp \left(-2 + 6\right)\\ \left(0 - 3\right) \amp \left(0 + 3\right) \amp \left(0 - 9\right)\end{array}\right]\\ \amp = \left[\begin{array}{ccc} 7 \amp -6 \amp 4\\ -3 \amp 3 \amp -9\end{array}\right] \end{align*}
We can generalize this procedure into an algorithm below.
def matrix_product(A, B):
  mA = number of rows in A
  mB = number of rows in B
  nA = number of columns in A
  nB = number of columns in B

  if nA not equal mB:
    print("Matrix dimensions are not compatible for multiplication.")
    return NULL

  matrix_product = an mA x nB array
  for row in [0, 1, ..., mA - 1]:
    for col in [0, 1, ..., nB - 1]:
      myEntry = 0
      for index in [0, 1, ..., nA - 1]:
        myEntry = myEntry + (A[row, index] * B[index, col])
      matrix_product[row, col] = myEntry

  return matrix_product
As we’ve done with the other algorithms we’ve presented, complete the following exercise to determine the run-time complexity of the matrix multiplication algorithm outlined above.

Checkpoint 7.2.14. Matrix Multiplication Complexity.

Try the following exercises to test your understanding of computing matrix products.

Checkpoint 7.2.15. Matrix Multiplication 1.

Checkpoint 7.2.16. Matrix Multiplication 2.

Checkpoint 7.2.17. Matrix Multiplication 3.

Checkpoint 7.2.18. Matrix Multiplication 4.

Subsection 7.2.5 Outer-products of one-dimensional arrays

At the end of the previous section, you were promised learning how to compute the outer-product between two one-dimensional arrays. We’ve blown by that, but will return to it now. With the addition of a simple initial step, computing the outer-product becomes a special case of the matrix multiplication you’ve just learned. Given two one-dimensional arrays, \(A\) and \(B\text{,}\) we’ll tip \(B\) on its side so that it becomes a row vector rather than a column vector. We’ll call this taking the transpose of \(B\text{,}\) and denote it by \(B^T\text{.}\) The new array \(B^T\) then has a single row. Since the array \(A\) has a single column, then matrix multiplication is defined between these two objects. If \(A\) is an array of length \(m\) and \(B\) is an array of length \(n\text{,}\) then the outer product \(AB^T\) is a two-dimensional array with \(m\) rows and \(n\) columns. See the example below.

Example 7.2.19. Compute the Outer-Product.

Given the arrays \(A = \left[\begin{array}{c}2\\ 3\end{array}\right]\) and \(B = \left[\begin{array}{c} -1\\ 0\\ 5\end{array}\right]\text{,}\) compute the outer-product \(AB^T\text{.}\)
Solution.
\begin{align*} AB^T \amp = \left[\begin{array}{c} 2\\ 3\end{array}\right]\cdot \left[\begin{array}{ccc} -1 \amp 0 \amp 5\end{array}\right]\\ \amp = \left[\begin{array}{ccc} 2\left(-1\right) \amp 2\left(0\right) \amp 2\left(5\right)\\ 3\left(-1\right) \amp 3\left(0\right) \amp 3\left(5\right)\end{array}\right]\\ \amp = \left[\begin{array}{ccc} -2 \amp 0 \amp 10\\ -3 \amp 0 \amp 15\end{array}\right] \end{align*}

Checkpoint 7.2.20. Compute the Outer Product.

Subsection 7.2.6 Conclusions

In this and the previous section you were exposed two one- and two-dimensional arrays. You’ve seen how simple mathematical operations, including scalar multiplication, addition/subtraction, and products. We saw that there are at least two ways to define vector products, including the inner- and outer-products. Spoiler alert, there are more, and you’ll encounter them elsewhere. We saw that multiplication is not a commutative operation with arrays. That is, \(AB\) is not generally the same as \(BA\) -- in fact, knowing that the product \(AB\) is defined doesn’t even guarantee that the product \(BA\) is defined.
In the final section of this chapter, we’ll simply introduce the notion that arrays with more than two dimensions exist and are quite useful. You’ve certainly encountered them whether you realize it or not. You’ll likely encounter these structures in your more advanced coursework. See you in the next section.
PrevTopNext