So far, there has been a great deal of terminology and mathematics that–I hope–are not too difficult or overwhelming because… it gets worse! :)
Here, we continue the inundation via mathematica and introduce some basic, foundational concepts of matrix algebra. Matrices are extensively used to represent graphs/networks. By extension, matrix algebra is the key for manipulating graphs to extract meaningful metrics from them.
It is not possible to be a “network analyst” if you don’t know the math. Full stop.
This page is just a sample of the multitude of matrix operations that are possible and is not exhaustive. That said, these foundational concepts will be invaluable as we read through papers and discuss methods for implementing graph theoretical techniques.
Note: Many of these materials are drawn from Zachary Fisher’s tutorials on Matrix Algebra.
Formally, a matrix is an array of numbers or expressions arranged by rows and columns. Matrices are always notated in \(\textbf{bold}\) lettering. Elements of a matrix are called cells and they are often referenced as the lowercase of the matrix’s “name”. Thus, a cell of \(\underset{i\times j}{\mathbf{A}}\) is \(a_{ij}\) where \(i\) refers to the row and \(j\) refers to the column of \(\mathbf{A}\).
Below, we see the matrix, \(\underset{i\times j}{\mathbf{A}}\) whose dimensions are \(i\) and \(j\):
\[ \underset{i\times j}{\mathbf{A}} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \]
In this case, the matrix, \(\mathbf{A}\) is also called, “square” which we discuss now.
Square matrices are matrices where the dimensions of the matrix, \(\underset{i\times j}{\mathbf{A}}\), are equal (i.e., \(i = j\)). These types of matrices are incredibly common in psychology as we typically apply statistical models to correlation or covariance matrices which are–by definition–square. Given that \(i\) and \(j\) are equivalent, we can then express \(\mathbf{A}\) as:
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \] Note the \(_n\) subscript on \(\mathbf{A}\) denoting that the dimensions are identical in row and column.
These forms of matrices are also square matrices with an additional constraint which is that they are identical “about their diagonal”. What does this mean? Let’s illustrate:
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} a_{a} & a_{ab} & a_{ac} \\ a_{ab} & a_{b} & a_{bc} \\ a_{ac} & a_{bc} & a_{c} \end{bmatrix} \] The square, symmetric matrix above has identical values on opposing sides of the diagonal. If you imagine folding the \(mathbf{A}\) matrix along the diagonal, the cells that would “touch” or overlap would be identical to one another.
Think back to when we worked on determining the maximum cardinality of \(E\) under the original definition of our graph. Would that table or matrix be square? What about symmetric?
This is where we make our first big connection to the graphs we discussed previously. The graph \(G = (V,E)\) under the original defintion of \(E\) was an undirected simple graph. The example we walked through to find the maximum theoretical cardinality of \(E\) was a matrix that was “symmetric” and “square”.
Matrices that are diagonal are square matrices that have information along their diagonals. Alternatively, one may say that they contain \(0.00\)’s along their “off-diagonal” elements. We illustrate that as:
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} a_{a} & 0 & 0 \\ 0 & a_{b} & 0 \\ 0 & 0 & a_{c} \end{bmatrix} \]
An identity matrix–often mathematically denoted as \(\mathbf{I}\) is a special case of diagonal matrices where the diagonal elements are all \(1.00\). This gives us:
\[ \underset{n\times n}{\mathbf{I}} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]
Math on matrices is not always as straight-forward as math for single values (i.e., scalars). This is because we do not do calculate cell-to-cell relationships but rather the relationships between cells and the rows and columns of the other matrix involved.
We’ll begin this discussion on matrix operations by beginning with the simplest operations that should–intuitively–make sense for many of you. Following that, we will move into the less intuitive matrix operations and a bit more challenging concepts.
In order to conduct addition on a pair of matrices, they must be of the same order. That is, they must have the same number of rows and columns. Say we have two matrics, \(\mathbf{A}\) and \(\mathbf{B}\) and we are trying to calculate the matrix, \(\mathbf{C}\):
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} 10 & 5\\ 9 & 1 \end{bmatrix}, \underset{n\times n}{\mathbf{B}} = \begin{bmatrix} 2 & 1\\ 20 & 0 \end{bmatrix}, \text{ then }\underset{?\times ?}{\mathbf{C}} = ? \]
As stated above, \(\mathbf{A}\) and \(\mathbf{B}\) must have the same order. In this case, they are both \(2\times 2\). The resulting matrix, \(\mathbf{C}\) will also be \(2\times 2\).
To calculate any given cell of \(\mathbf{C}\), we simply add the terms that exist in the same cells of each matrix:
\[a_{11} + b_{11} = c_{11}\] \[10 + 2 = 12\] If we repeat this for all cells, we eventually get:
\[ \underset{n\times n}{\mathbf{C}} = \begin{bmatrix} 12 & 6\\ 29 & 1 \end{bmatrix} \]
What is the matrix sum of the following:
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} \sqrt{64} & 15\\ 18 & -5 \end{bmatrix}, \underset{n\times n}{\mathbf{B}} = \begin{bmatrix} \frac{130}{10} & 10\\ 10 & -29 \end{bmatrix}, \text{ then }\underset{?\times ?}{\mathbf{C}} = ? \]
\[ \underset{n\times n}{\mathbf{C}} = \begin{bmatrix} 21 & 25\\ 28 & -34 \end{bmatrix} \] We could also do this math in \(\texttt{R}\):
A = matrix(c(sqrt(64), 15,
18, -5),
nrow = 2, ncol = 2,
byrow = TRUE)
B = matrix(c(130/10, 10,
10, -29),
nrow = 2, ncol = 2,
byrow = TRUE)
A [,1] [,2]
[1,] 8 15
[2,] 18 -5B [,1] [,2]
[1,] 13 10
[2,] 10 -29A + B [,1] [,2]
[1,] 21 25
[2,] 28 -34What then, is the sum of the matrix \(\mathbf{A}\) and a \(1\times 1\) matrix with the value of \(5\)?
If 5 is a \(1\times 1\) matrix then the problem is not possible to solve We will verify this in \(\texttt{R}\):
# If 5 is a matrix
A = matrix(c(sqrt(64), 15,
18, -5),
nrow = 2, ncol = 2,
byrow = TRUE)
B = matrix(5,
nrow = 1, ncol = 1,
byrow = TRUE)
A [,1] [,2]
[1,] 8 15
[2,] 18 -5 B [,1]
[1,] 5 A + B # fails to workError in A + B: non-conformable arrays# But why does the below work?
# What is R doing "under the hood"?
A + 5 [,1] [,2]
[1,] 13 20
[2,] 23 0Matrix addition also exhibits the commutative and associative laws. That is:
\[\mathbf{A} + \mathbf{B} = \mathbf{B} + \mathbf{A}\] and \[\mathbf{A} + (\mathbf{B} + \mathbf{C}) = (\mathbf{A} + \mathbf{B}) + \mathbf{C}\] and \[\mathbf{A} + (-\mathbf{B}) = (\mathbf{A} - \mathbf{B})\]
Matrix subtraction works identically to matrix addition. Given any pair of matrices of the same order we can simply subtract element-wise.
Let’s work through an example:
\[ \underset{n\times n}{\mathbf{A}} = \begin{bmatrix} 37 & -91\\ 0 & 26 \end{bmatrix}, \underset{n\times n}{\mathbf{B}} = \begin{bmatrix} 1 & 27\\ 13 & 22 \end{bmatrix}, \text{ then }\underset{?\times ?}{\mathbf{C}} = ? \]
Next, we can verify our solution in \(\texttt{R}\):
(A = matrix(c(37, -91,
0, 26),
nrow = 2,
ncol = 2,
byrow = TRUE)) [,1] [,2]
[1,] 37 -91
[2,] 0 26(B = matrix(c(1, 27,
13, 22),
nrow = 2,
ncol = 2,
byrow = TRUE)) [,1] [,2]
[1,] 1 27
[2,] 13 22A - B [,1] [,2]
[1,] 36 -118
[2,] -13 4Matrix multiplication is where things become a bit confusing for some folks who are unfamiliar with matrix algebra. There are some heuristics to remember when attempting matrix multiplication:
We illustrate the logic here:
\[ \underset{2\times 3}{\mathbf{A}} = \begin{bmatrix} \colorbox{#EEBC1D}{$a_{11}$} & \colorbox{#EEBC1D}{$a_{12}$} & \colorbox{#EEBC1D}{$a_{13}$}\\[6pt] a_{21} & a_{22} & a_{23} \end{bmatrix},\quad \underset{3\times 2}{\mathbf{B}} = \begin{bmatrix} \colorbox{#EEBC1D}{$b_{11}$} & b_{12}\\[6pt] \colorbox{#EEBC1D}{$b_{21}$} & b_{22}\\[6pt] \colorbox{#EEBC1D}{$b_{31}$} & b_{32} \end{bmatrix},\quad \underset{2\times 2}{\mathbf{AB}} = \begin{bmatrix} \colorbox{#EEBC1D}{$ab_{11} = (a_{11}\times b_{11}) + (a_{12}\times b_{21}) + (a_{13}\times b_{31})$} & \cdots\\[6pt] \cdots & \cdots \end{bmatrix} \]
Matrix multiplications have the associative property. That is, moving the order in which matrix were multiplied will not change the resulting product matrix:
\[(\mathbf{A}\mathbf{B})\mathbf{C} = \mathbf{A}(\mathbf{B}\mathbf{C})\]
Matrix products are also distributive with respect to addition:
\[\mathbf{A}(\mathbf{B} + \mathbf{C}) = \mathbf{A}\mathbf{B} + \mathbf{A}\mathbf{C}\]
Likewise, if we have a scalar–a single value–\(c\), then:
\[c(\mathbf{A}\mathbf{B}) = (c\mathbf{A})\mathbf{B} = \mathbf{A}(c\mathbf{B}) = (\mathbf{A}\mathbf{B})c\] Multiplication by a scalar will often just look like a lowercase letter–the scalar–multiplied by a bold character representing the matrix:
\[ k\mathbf{A} \]
\[ \underset{2\times 2}{\mathbf{A}} = \begin{bmatrix} 10 & 5\\ 9 & 1 \end{bmatrix}, k = 2, \text{ then } k\mathbf{A} = \begin{bmatrix} 20 & 10\\ 18 & 2 \end{bmatrix} \]
Once again, we verify in \(\texttt{R}\):
(A = matrix(c(10, 5,
9, 1),
nrow = 2,
ncol = 2,
byrow = TRUE)) [,1] [,2]
[1,] 10 5
[2,] 9 1(k = 2)[1] 2k*A [,1] [,2]
[1,] 20 10
[2,] 18 2When we add a scalar to a matrix in \(\texttt{R}\), it is essentially adding “element-wise”. So, it’s taking the single value and adding it to each element of the matrix.
Another way of thinking about this is that \(\texttt{R}\) is multiplying our scalar by a matrix of 1’s, commonly referred to as the \(\mathbf{J}\) matrix which looks like this:
\[ \underset{2\times 2}{\mathbf{J}} = \begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix} \]
Thus:
(A = matrix(c(10, 5,
9, 1),
nrow = 2,
ncol = 2,
byrow = TRUE)) [,1] [,2]
[1,] 10 5
[2,] 9 1k = 2
A + k [,1] [,2]
[1,] 12 7
[2,] 11 3# Is the same as:
(J = matrix(c(1, 1,
1, 1),
nrow = 2,
ncol = 2)) [,1] [,2]
[1,] 1 1
[2,] 1 1A + (k*J) [,1] [,2]
[1,] 12 7
[2,] 11 3# Where:
(k*J) [,1] [,2]
[1,] 2 2
[2,] 2 2The transpose of a matrix is an operation which flips a matrix over its diagonal. That is, it switches the row and column indices of the matrix \(\mathbf{A}\) by producing another matrix, often denoted as \(\mathbf{A}'\) or \(\mathbf{A}^{T}\).
Some useful properties of the matrix transpose include:
Here’s a color-coded example to help solidify the example:
\[ \underset{3\times 3}{\mathbf{A}} = \begin{bmatrix} \colorbox{#EEBC1D}{$1$} & \colorbox{#8CD0FF}{$2$} & \colorbox{#8CD0FF}{$3$}\\[6pt] \colorbox{#9EE493}{$4$} & \colorbox{#EEBC1D}{$5$} & \colorbox{#8CD0FF}{$6$}\\[6pt] \colorbox{#9EE493}{$7$} & \colorbox{#9EE493}{$8$} & \colorbox{#EEBC1D}{$9$} \end{bmatrix},\quad \underset{3\times 3}{\mathbf{A}'} = \begin{bmatrix} \colorbox{#EEBC1D}{$1$} & \colorbox{#9EE493}{$4$} & \colorbox{#9EE493}{$7$}\\[6pt] \colorbox{#8CD0FF}{$2$} & \colorbox{#EEBC1D}{$5$} & \colorbox{#9EE493}{$8$}\\[6pt] \colorbox{#8CD0FF}{$3$} & \colorbox{#8CD0FF}{$6$} & \colorbox{#EEBC1D}{$9$} \end{bmatrix} \]
Here, the highlighted diagonal entries show how transposition flips a matrix over its main diagonal, exchanging rows and columns.
We can verify in R and demonstrate the transpose and how it visually appears:
(A = matrix(c(1,2,3,
4,5,6,
7,8,9),
nrow = 3,
byrow = TRUE)) [,1] [,2] [,3]
[1,] 1 2 3
[2,] 4 5 6
[3,] 7 8 9t(A) [,1] [,2] [,3]
[1,] 1 4 7
[2,] 2 5 8
[3,] 3 6 9The trace of a matrix is the sum of elements along its main diagonal and is defined only for square matrices. For an \(n\times n\) matrix \(\mathbf{A}\), the trace is:
\[ tr(\mathbf{A}) = \sum_{i=1}^{n} a_{ii} = a_{11} + a_{22} + \dots + a_{nn} \]
Some useful properties of the matrix trace include:
We illustrate the trace with color highlights to clearly show the diagonal elements that contribute to the trace:
\[ \underset{3\times 3}{\mathbf{A}} = \begin{bmatrix} \colorbox{#EEBC1D}{$1$} & 2 & 3\\[6pt] 4 & \colorbox{#EEBC1D}{$5$} & 6\\[6pt] 7 & 8 & \colorbox{#EEBC1D}{$9$} \end{bmatrix}, \quad tr(\mathbf{A}) = 1 + 5 + 9 = 15 \]
We can verify in R and demonstrate how to take the trace of a matrix:
(A = matrix(c(1,2,3,
4,5,6,
7,8,9),
nrow = 3,
byrow = TRUE)) [,1] [,2] [,3]
[1,] 1 2 3
[2,] 4 5 6
[3,] 7 8 9sum(diag(A))[1] 15As I mentioned at the beginning of this section, matrix operations are the backbone of a significant portion of graph theory and network analysis. Having a strong understanding of these operations and what they imply it crucial for success in this area of work.
There are many more operations and much more complex operations we are leaving out for the time being. We will discuss these other terms as they become relevant.
In the next–and final–section for this first week, we will talk about the most important matrix in graph theory and network analysis:
The Adjacency Matrix