Read connection sums and symmetry
A connection matrix records direct links between an ordered list of vertices. Adding a row or column gives a connection count, and an undirected network produces a symmetric matrix
\[m_{ij}=m_{ji}\text{ for every }i,j\quad\Rightarrow\quad M=M^T\]
- Keep one vertex order Use the same vertex order for the rows and columns of the connection matrix \(\displaystyle m_{ij}=\text{number of direct links from }i\text{ to }j\)
- Add along the required axis A row sum counts connections leaving a vertex, while a column sum counts connections arriving at a vertex \(\displaystyle \text{row }i:\sum_jm_{ij},\quad\text{column }j:\sum_im_{ij}\)
- Count a loop on the diagonal A loop at a vertex is recorded in its leading-diagonal entry and contributes once to the relevant sum \(\displaystyle m_{ii}=1\quad\Rightarrow\quad\text{one loop at vertex }i\)
- Compare mirrored entries If every connection is two-way, every pair of mirrored entries is equal and the matrix is symmetric. One matching pair alone does not establish symmetry \(\displaystyle m_{ij}=m_{ji}\text{ for every }i,j\quad\Rightarrow\quad M=M^T\)
Worked example
The connection matrix for vertices A, B and C is shown below. Find the direct connection count for B and decide whether the matrix is symmetric
\[M=\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}\]
- \(\displaystyle \text{column B}=1+0+1=2\)Adding the B column counts the direct connections arriving at B
- \(\displaystyle \text{row B}=1+0+1=2\)Adding the B row also gives 2 because every connection in this matrix is two-way
- \(\displaystyle m_{12}=m_{21}=1,\quad m_{13}=m_{31}=2,\quad m_{23}=m_{32}=1\)Each off-diagonal entry agrees with its mirrored entry
- \(\displaystyle M=M^T\quad\Rightarrow\quad M\text{ is symmetric}\)The matrix is symmetric, and vertex B has 2 direct connections
Common mistakes
Checking only the diagonal
✕\(\displaystyle m_{11}=m_{22}=m_{33}=0\quad\Rightarrow\quad M=M^T\)✓\(\displaystyle m_{ij}=m_{ji}\text{ for every }i,j\quad\Rightarrow\quad M=M^T\)
Diagonal entries compare with themselves, so symmetry must be checked with every pair of mirrored positionsTreating a connection sum as a vertex count
✕\(\displaystyle \text{column sum}=3\quad\Rightarrow\quad\text{there are 3 vertices}\)✓\(\displaystyle \text{column sum}=3\quad\Rightarrow\quad\text{the vertex has 3 direct connections}\)
A row or column sum adds connection entries for one vertex; it does not count the vertices in the whole networkMirroring a one-way connection
✕\(\displaystyle M=\begin{bmatrix}0&1\\1&0\end{bmatrix}\quad\text{for the one-way link }A\to B\)✓\(\displaystyle M=\begin{bmatrix}0&1\\0&0\end{bmatrix}\quad\text{for the one-way link }A\to B\)
A one-way link is recorded in one directed position, so it is not copied into the mirrored positionDifficulty levels
introAdd a row or column of an undirected connection matrix and state its meaning
standardUse sums, symmetry and a comparison of connection counts in a larger undirected matrix
challengeDistinguish row and column sums for a directed network and count a loop consistently
examChoose a correct connection sum, meaning or symmetry statement
Questions about this topic
What does a row sum mean in a connection matrix?+
With rows recording the starting vertex, a row sum counts the direct connections leaving that vertex
When is a connection matrix symmetric?+
It is symmetric exactly when every mirrored pair has equal counts: the entry in row i and column j equals the entry in row j and column i for every pair of vertices. Equal row and column sums alone are not sufficient
What does a diagonal entry represent?+
A diagonal entry records a connection from a vertex to itself, such as a loop, and contributes to that vertex's sum
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 11, VCE Units 1 & 2, General Mathematics, chapter 4: Matrices
In this chapter
State the order of a matrix and locate its elements4A Matrix types and order: Identify row, column, square, symmetric and zero matricesRead information from a labelled data matrix4B Matrix addition and subtraction: Identify row, column, square, symmetric and zero matricesAdd and subtract matrices4B Matrix addition and subtraction: Find unknown entries in a matrix equationMultiply a matrix by a scalarCombine scalar multiples of matricesDecide whether a matrix product is defined and give its orderMultiply matrices4D Matrix products and powers: Evaluate powers of a square matrixIdentify and construct the identity matrix4E Inverse matrices and simultaneous equations: Find unknown entries in a matrix equationFind the determinant of a 2 × 2 matrixFind the inverse of a 2 × 2 matrixWrite simultaneous equations as a matrix equationSolve simultaneous equations using the inverse matrix4F Matrices for networks: Evaluate powers of a square matrixRepresent a network in a matrixIdentify the network a connection matrix describesInterpret connection sums and symmetryCount routes using powers of a connection matrixSet up a transition matrixUse a transition matrix to predict the next step4H State matrices and recurrence: Evaluate powers of a square matrixGenerate state matrices by recursionDetermine the long-run state of a transition modelUse matrix multiplication to answer an application questionUse row and column matrices of ones to extract totals