Matrix

A matrix is some table of numbers, symbols, or mathematical objects coming from a set. A matrix has a “height” and a “width” corresponding to the number of rows and the number of columns, respectively. We describe a matrix first by its number of rows and then by its number of columns. A “two by three matrix of integers”, shown below, has two rows, three columns, and its entries are integers.

\[\begin{split}\begin{split} \begin{bmatrix} 3 & 5 & 12 \\ -1 & -7 & 4 \end{bmatrix} \end{split}\end{split}\]

For a particular \((i, j)\) index, we can say the \((i, j) \text{th}\) entry of a matrix is the element of the matrix in the \(i \text{th}\) row and the \(j \text{th}\) column. In the previous matrix, \(5\) is the \((1, 2)\) entry; \(-7\) is the \((2, 1)\) entry. Generally, we can have an \(m\) by \(n\) matrix with \(m\) rows and \(n\) columns. An \(m\) by \(n\) matrix can be denoted as \(A_{m \times n}\).

We give special names to matrices with certain dimensions:

1. When \(m = 1\), we have a row vector. Below is a row vector with 7 entries.

\[\begin{bmatrix} 4 & 1 & 4 & 2 & 3 & 7 & 8 \end{bmatrix}\]

2. When \(n = 1\), we have a column vector. Below is a column vector with 6 entries.

\[\begin{split}\begin{split} \begin{bmatrix} 5 \\ -3 \\ 4 \\ -11 \\ 22 \\ 6 \end{bmatrix} \end{split}\end{split}\]

3. When \(m = n\), we have a square matrix. We say a square matrix is of order \(n\) for a matrix with dimension \(n\) by \(n\). A square matrix of order \(3\) is shown below.

\[\begin{split}\begin{split} \begin{bmatrix} 9 & -1 & 16 \\ 3 & -5 & 12 \\ 11 & 4 & -8 \end{bmatrix} \end{split}\end{split}\]

Operations

When matrices have entries coming from a set with supports addition and multiplication, like real numbers, integers, or even more general objects like polynomials, it is possible to combine them when a generalized form of arithmetic.

Scalar Multiplication

Scalar multiplication is a simple operation which multiplies a single number against each entry of a matrix to produce another matrix of the same dimensions.

Say \(A = (a_{i, j})\) is an \(m\) by \(n\) integer matrix. Given some other integer \(c\), \(cA\) is another \(m\) by \(n\) matrix where:

\[\begin{split}\begin{split}cA = (c \cdot a_{i,j}) &= c\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \\ \end{bmatrix} \\[1em] & = \begin{bmatrix} c\cdot a_{1,1} & c\cdot a_{1,2} & \cdots & c\cdot a_{1,n} \\ c\cdot a_{2,1} & c\cdot a_{2,2} & \cdots & c\cdot a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ c\cdot a_{m,1} & c\cdot a_{m,2} & \cdots & c\cdot a_{m,n} \\ \end{bmatrix} \end{split}\end{split}\]

Example

\[\begin{split}\begin{split} A = \begin{bmatrix} 3 & 5 & 12 \\ -1 & -7 & 4 \end{bmatrix} \qquad 4A = \begin{bmatrix} 12 & 20 & 48 \\ -4 & -28 & 16 \end{bmatrix} \end{split}\end{split}\]

Addition and Subtraction

Two matrices can be added or subtracted when they have the same dimensions. For two \(m\) by \(n\) matrices, \(A = (a_{i, j})\) and \(B = (b_{i, j})\), their sum \(A + B\) is equal to \((a_{i, j} + b_{i, j})\). That is, each entry of \(A\) is added to the corresponding entry in \(B\) in the same position.

\[\begin{split}\begin{aligned} \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \\ \end{bmatrix} + \begin{bmatrix} b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\ b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{m,1} & b_{m,2} & \cdots & b_{m,n} \\ \end{bmatrix} &= \\[1em] \begin{bmatrix} a_{1,1} + b_{1,1} & a_{1,2} + b_{1,2} &\cdots & a_{1,n} + b_{1,n} \\ a_{2,1} + b_{2,1} & a_{2,2} + b_{2,2} & \cdots & a_{2,n} + b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} + b_{m,1} & a_{m,2} + b_{m,2} & \cdots & a_{m,n} + b_{m,n} \\ \end{bmatrix} & \end{aligned}\end{split}\]

By scalar multiplication, we can define subtraction via addition:

\[A - B = A + (-1)B\]

To add or subtract matrices they must be of the same dimensions. Every entry in the first matrix must have a corresponding entry in the second matrix to be added to.

Example

\[\begin{split}\begin{split} \begin{bmatrix} 1 & -4 & 8\\ 11 & 2 & 24 \\ 12 & 4 & 1 \\ \end{bmatrix} + \begin{bmatrix} -9 & 8 & 6 \\ 0 & 15 & 2 \\ 3 & 14 & 0 \end{bmatrix} = \begin{bmatrix} -8 & 4 & 14 \\ 11 & 17 & 26 \\ 15 & 18 & 1 \end{bmatrix} \end{split}\end{split}\]

Matrix Multiplication

Matrix multiplication is much more involved than addition. First, we must consider under which conditions two matrices can be multiples.

Matrix multiplication between two matrices is only defined when the number of columns in the left-hand matrix equals the number of rows in the right-hand matrix. The result of the multiplication is another matrix whose number of rows equals the left-hand matrix’s and whose number of columns equals the right-hand matrix’s.

\[A_{m\times n} \cdot B_{n\times p} = C_{m \times p}\]

In this notation, the “inner” dimensions must be the same, and the “outer” dimensions give the dimensions of the product. In this case, \(n = n\) are the inner dimensions, and \(m, p\) are the outer dimensions.

But how do we define the entries of the product \(C = (c_{i, j})\)? Each entry of the matrix product \(c_{i, j}\) is an inner product of the \(i \text{th}\) row of \(A\) and the \(j \text{th}\) column of B.

\[\begin{split}\begin{split} c_{i,j} &= \begin{bmatrix} a_{i,1} & a_{i,2} & a_{i,3} & \cdots & a_{i,n} \\ \end{bmatrix} \cdot \begin{bmatrix} b_{1,j} \\ b_{2,j} \\ b_{3,j} \\ \vdots \\ b_{n,j} \\ \end{bmatrix} \\[1em] &= \left(a_{i,1}\cdot b_{1,j} + a_{i,2} \cdot b_{2,j} + \cdots + a_{i,n}\cdot b_{n,j}\right) \\[1em] &= \sum_{k=1}^n a_{i,k} \cdot b_{k,j} \end{split}\end{split}\]

Therefore, the matrix multiplication \(A_{m\times n} \cdot B_{n\times p} = C_{m \times p}\) is actually \(m \times p\) individual inner products.

A \(4\) by \(4\) matrix multiplication showing the inner product producing \(c_{2, 2}\).

Example

\[\begin{split}\begin{split} \begin{bmatrix} -9 & 6 \\ 0 & 2 \\ 3 & 0 \end{bmatrix}_{3\times\textcolor{green}{2}} & \times \begin{bmatrix} 1 & -4 & 5 \\ 7 & 2 & 2 \\ \end{bmatrix}_{\textcolor{green}{2}\times3} \\[1em] & = \begin{bmatrix} (-9 \cdot 1) + (6 \cdot 7) & (-9\cdot -4) + (6 \cdot 2) & (-9 \cdot 5) + (6 \cdot 2) \\ (0 \cdot 1) + (2 \cdot 7) & (0\cdot -4) + (2 \cdot 2) & (0 \cdot 5) + (2 \cdot 2) \\ (3 \cdot 1) + (0 \cdot 7) & (3\cdot -4) + (0 \cdot 2) & (3 \cdot 5) + (0 \cdot 2) \\ \end{bmatrix}_{3\times3} \\[1em] & = \begin{bmatrix} 33 & 48 & -33 \\ 14 & 4 & 4 \\ 3 & -12 & 15 \\ \end{bmatrix}_{3\times3}\end{split}\end{split}\]

Important

Matrix multiplication is not commutative. In general, \(AB \neq BA\).

Zero and Identity Matrices

It is sometimes possible for \(AB = BA\). Two important examples are when one of the matrices is the zero matrix or the identity matrix.

Zero matrix

The zero matrix is a matrix with all zero entries. The \(m\) by \(n\) zero matrix is denoted by \(0_{m, n}\).

\[\begin{split}\begin{split} 0_{m,n} = \left.\begin{bmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots &0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \\ \end{bmatrix}\ \right\} \small{m \text{ rows}} \end{split}\end{split}\]

Assuming matrix multiplication is defined, the product of a zero matrix by any other matrix is the zero-matrix (of possibly different dimension).

Example

\[\begin{split}\begin{split} \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 & 6 \\ 5 & 3 & 3 \\ \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \end{split}\end{split}\]

For a matrix \(A = (a_{i, j})\), its main diagonal is the entries \(a_{i, j}\) for which \(i = j\). In a square matrix of order \(n\), there are \(n\) entries along the main diagonal. In a rectangular matrix, the smaller of the two dimensions determines the number of entries along the main diagonal.

\[\begin{split}\begin{split} \begin{bmatrix} \textcolor{green}{x} & 0 & 0 \\ 0 & \textcolor{green}{y} & 0 \\ 0 & 0 & \textcolor{green}{z} \\ \end{bmatrix} \qquad \begin{bmatrix} \textcolor{green}{x} & 0 & 0 \\ 0 & \textcolor{green}{y} & 0 \\ 0 & 0 & \textcolor{green}{z} \\ 0 & 0 & 0 \\ \end{bmatrix} \qquad \begin{bmatrix} \textcolor{green}{x} & 0 & 0 & 0 \\ 0 & \textcolor{green}{y} & 0 & 0\\ 0 & 0 & \textcolor{green}{z} & 0\\ \end{bmatrix} \end{split}\end{split}\]

Note that the other entries need to be \(0\). For example, the three main diagonals of the matrices in the zero multiplication example are \((0, 0)\), \((2, 3)\), and \((0, 0, 0)\). If all entries not on the main diagonal are \(0\), then we call that matrix a diagonal matrix.

Identity matrix

The identity matrix is a square diagonal matrix with all entries of the main diagonal equal to \(1\). The identity matrix of order \(n\) is denoted \(I_n\).

The property of the identity matrix is that any other matrix multiplied by the identity is equal to itself. For an \(m\) by \(n\) matrix \(A\), we have:

\[I_mA = AI_n = A.\]

If \(A\) is a square matrix of order \(n\), then we have:

\[I_nA = AI_n = A.\]

We can also leave the order of the identity matrix implicit. For an \(m\) by \(n\) matrix \(A\), we write \(AI\) to mean \(A\) times \(I_n\). The dimensions of the other matrix dictate the order of the identity matrix.

Example

\[\begin{split}\begin{split} \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 & 6 \\ 5 & 3 & 3 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 & 6 \\ 5 & 3 & 3 \\ \end{bmatrix} \\[1em] \begin{bmatrix} 2 & 1 & 6 \\ 5 & 3 & 3 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 & 6 \\ 5 & 3 & 3 \\ \end{bmatrix} \end{split}\end{split}\]

Power of Matrices

For square matrices, we can define the power of a matrix as the repeated multiplication of the matrix with itself.

Let \(A\) be a square matrix of order \(n\). Then:

\[A^0 = I_n, \qquad\qquad A^2 = AA, \qquad\qquad A^3 = AAA, \qquad\qquad\text{etc.}\]

Example

\[\begin{split}\begin{split} \begin{bmatrix} 2 & 6 \\ 5 & 3 \\ \end{bmatrix}^2 &= \begin{bmatrix} 2 & 6 \\ 5 & 3 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 6 \\ 5 & 3 \\ \end{bmatrix} \\[1em] &= \begin{bmatrix} 34 & 30 \\ 25 & 39 \\ \end{bmatrix}\end{split}\end{split}\]

Matrix Transpose

A transpose is an operation performed on a matrix which reverses its dimensions. In particular, it exchanges the rows of the matrix with its columns.

Given an \(m\) by \(n\) matrix \(A\), its transpose is denoted \(A^T\) and is an \(n\) by \(m\) matrix. \(A^T\) is defined as:

\[\begin{split}\begin{split} A &= (a_{i,j}) = \begin{bmatrix} a_{1,1} & \textcolor{green}{a_{1,2}} & \cdots & a_{1,n} \\ a_{2,1} & \textcolor{green}{a_{2,2}} & \cdots & a_{2,n} \\ a_{3,1} & \textcolor{green}{a_{3,2}} & \cdots & a_{3,n} \\ a_{4,1} & \textcolor{green}{a_{4,2}} & \cdots & a_{4,n} \\ \vdots & \textcolor{green}{\vdots} & \ddots & \vdots \\ a_{m,1} & \textcolor{green}{a_{m,2}} & \cdots & a_{m,n} \\ \end{bmatrix} \\[1em] A^T &= (a_{j,i}) = \begin{bmatrix} a_{1,1} & a_{2,1} & a_{3,1} & a_{4,1} & \cdots & a_{m,1} \\ \textcolor{green}{a_{1,2}} & \textcolor{green}{a_{2,2}} & \textcolor{green}{a_{3,2}} & \textcolor{green}{a_{4,2}} & \textcolor{green}{\cdots} & \textcolor{green}{a_{m,2} }\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{1,n} & a_{2,n} & a_{3,n} & a_{4,n} & \cdots & a_{m,n} \\ \end{bmatrix} \end{split}\end{split}\]

Notice that the second column becomes the second row.

Since a transpose changes the dimensions, the transpose of a “tall” matrix is a “wide” matrix. Visually, matrix transposition “flips” or “rotates” the entries of the matrix along its main diagonal. The entries on the main giagonal do not change.

Animated matrix transpose.

Matrix transposition is easily reversible. Simply apply the transpose a second time.

\[A = {(A^T)}^T\]

Notice also that the identity matrix is not affected by transposition.

\[I = I^T = {I^T}^T\]

Zero-One Matrices

A special class of matrices whose entries come from the set \(\{0, 1\}\) are called zero-one matrices. These matrices have numerous and important applications in computer science. Indeed, \(\{0, 1\}\) may represent binary digits, ubiquitous in computer science.

Moreover, we can use \(\{0, 1\}\) to encode truth values false and true, respectively. This extends propositional logic to matrices.

See also

Propositions – Connectives

Join and Meet

FOr two zero-one matrices, we can define operations similar to matrix addition, but using \(\wedge\) and \(\vee\) isntead of \(+\). Let \(A = (a_{i, j})\) and \(B = (b_{i, j})\) be \(m\) by \(n\) matrices.

The join of \(A\) and \(B\) is the \(m\) by \(n\) zero-one matrix defined as:

\[A \lor B = (a_{i,j} \lor b_{i,j})\]

The meet of \(A\) and \(B\) is the \(m\) by \(n\) zero-one matrix defined as:

\[A \land B = (a_{i,j} \land b_{i,j})\]

Example

\[\begin{split}\begin{split} A = \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 0 \\ \end{bmatrix} \qquad\qquad B = \begin{bmatrix} 0 & 1 & 1\\ 1 & 1 & 0\\ \end{bmatrix} \end{split}\end{split}\]

The join of \(A\) and \(B\) is:

\[\begin{split}\begin{split} A \lor B = \begin{bmatrix} 1 \lor 0 & 0 \lor 1 & 1 \lor 1\\ 0 \lor 1& 1 \lor 1& 0 \lor 0\\ \end{bmatrix} =\ \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ \end{bmatrix} \end{split}\end{split}\]

The meet of \(A\) and \(B\) is:

\[\begin{split}\begin{split} A \land B = \begin{bmatrix} 1 \land 0 & 0 \land 1 & 1 \land 1\\ 0 \land 1& 1 \land 1& 0 \land 0\\ \end{bmatrix} =\ \begin{bmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix} \end{split}\end{split}\]

Boolean Product

Similar to matrix multiplication, we can define a multiplication-like operation using zero-one matrices.

The typical inner product used matrix multiplication replaced by a “disjunction of conjunctions”.

Let \(A\) be an \(m\) by \(n\) zero-one matrix and \(B\) be an \(n\) by \(o\) zero-one matrix. The boolean product of \(A\) and \(B\), denoted \(A \odot B\) is an \(m\) by \(p\) zero-one matrix with elements \(c_{i, j}\) defiend as:

\[\begin{split}\begin{split} c_{i,j} &= \begin{bmatrix} a_{i,1} & a_{i,2} & a_{i,3} & \cdots & a_{i,n} \\ \end{bmatrix} \odot \begin{bmatrix} b_{1,j} \\ b_{2,j} \\ b_{3,j} \\ \vdots \\ b_{n,j} \\ \end{bmatrix} \\[1em] &= \left(a_{i,1}\land b_{1,j}) \ \ \lor\ \ (a_{i,2} \land b_{2,j}) \ \ \lor\ \ \cdots \ \ \lor\ \ (a_{i,n}\land b_{n,j}\right) \\[1em] \end{split}\end{split}\]

Example

\[\begin{split}\begin{split} \begin{bmatrix} 1 & 0\\ 0 & 1\\ 1 & 0\\ \end{bmatrix} &\odot \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix}\\[1em] &= \begin{bmatrix} (1 \land 1) \lor (0 \land 0) & (1\land 1) \lor (0 \land 1) & (1 \land 0) \lor (0 \land 1) \\ (0 \land 1) \lor (1 \land 0) & (0\land 1) \lor (1 \land 1) & (0 \land 0) \lor (1 \land 1) \\ (1 \land 1) \lor (0 \land 0) & (1\land 1) \lor (0 \land 1) & (1 \land 0) \lor (0 \land 1) \\ \end{bmatrix}\\[1em] &= \begin{bmatrix} 1 \lor 0 & 1 \lor 0 & 0 \lor 0 \\ 0 \lor 0 & 0 \lor 1 & 0 \lor 1 \\ 1 \lor 0 & 1 \lor 0 & 0 \lor 0 \\ \end{bmatrix}\\[1em] &= \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix} \end{split}\end{split}\]

For square zero-one matrices, we can extend Boolean product to Boolean power. Denote \(A^{[n]}\) the Boolean product product of \(A\) with itself \(n\) times. Since Boolean products are associative, the order of operations does not matter for a Boolean power.

\[A^{[2]} = A \odot A, \qquad A^{[3]} = A^{[2]} \odot A = A \odot A^{[2]} = A \odot A \odot A, \qquad \text{etc.}\,\]

---

Source

Matrices — Discrete Structures for Computing