Analyse a relation matrix
Fix rows as sources and columns as targets before interpreting a directed relation matrix. The direct matrix records one-step relations, while a power of the matrix counts routes of the corresponding exact length
\[R^{2}_{ij}=r_{i1}r_{1j}+r_{i2}r_{2j}+r_{i3}r_{3j}\]
- Read rows as sources An entry in row i and column j describes a direct relation from i to j \(\displaystyle R_{23}=1\)
- Use zero for no direct self-relation A diagonal entry is 1 only when the relation from a vertex to itself is direct \(\displaystyle R_{11}=0\)
- Use powers for exact routes The ij entry of R squared counts routes from i to j using exactly two direct steps \(\displaystyle R^{2}_{13}=r_{11}r_{13}+r_{12}r_{23}+r_{13}r_{33}\)
- Score a dominance relation by row For a dominance relation, add the direct and two-step entries across each source row \(\displaystyle s_i=\sum_j(D_{ij}+D^{2}_{ij})\)
Worked example
A directed relation on vertices 1, 2 and 3 has matrix C below. Find the number of routes from vertex 2 to vertex 1 using exactly two steps
\[C=\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\end{bmatrix}\]
- \(\displaystyle C_{2\bullet}=[0\quad0\quad1],\quad C_{\bullet1}=\begin{bmatrix}0\\0\\1\end{bmatrix}\)Use row 2 as the source row and column 1 as the target column
- \(\displaystyle 0\times0=0,\quad0\times0=0,\quad1\times1=1\)These products count the possible intermediate vertices 1, 2 and 3
- \(\displaystyle C^{2}_{21}=0+0+1=1\)There is one route of exactly two steps from vertex 2 to vertex 1
Common mistakes
Reading two-step routes from the direct matrix
✕\(\displaystyle C^{2}_{21}=C_{21}=0\)✓\(\displaystyle C^{2}_{21}=0\times0+0\times0+1\times1=1\)
The direct matrix records one-step relations, whereas its square counts routes using exactly two stepsSquaring entries one at a time
✕\(\displaystyle C^{2}_{21}=C_{21}^{2}=0\)✓\(\displaystyle C^{2}_{21}=0\times0+0\times0+1\times1=1\)
Matrix powers use row-by-column products through every possible intermediate vertex, not entrywise powersReversing dominance direction
✕\(\displaystyle D_{21}=1\)✓\(\displaystyle D_{12}=1,\quad D_{21}=0\)
Rows are sources and columns are targets, so a relation from 1 to 2 is recorded at D12 rather than D21Difficulty levels
introRead a compact direct relation matrix and find a row total
standardUse a communication matrix to count two-step routes and direct diagonal returns
challengeUse D plus D squared to rank a dominance relation and identify ties
examChoose the correct relation matrix, route count or dominance result from alternatives
Questions about this topic
What does an entry of R to the power k count?+
In a binary relation matrix, the entry in row i and column j of R to the power k counts routes from i to j using exactly k direct steps
Why can a power have a non-zero diagonal entry?+
A non-zero diagonal entry in a power records a route that returns to its starting vertex in that exact number of steps. It does not imply a direct self-relation
How is a dominance score formed?+
For each source row, add the direct and two-step entries across the row of D plus D squared. Equal row totals produce a tie
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 12, VCE Units 3 & 4, General Mathematics, chapter 10: Matrices
In this chapter
State the order of a matrix and locate its elementsIdentify row, column, square, symmetric and zero matricesRead information from a labelled data matrixRead, transpose and classify a matrixConstruct a matrix from labelled information or an entry rule10A Matrix notation, types and construction: Solve a matrix equation10A Matrix notation, types and construction: Construct, apply and invert a permutation matrixAdd and subtract matricesFind unknown entries in a matrix equationMultiply a matrix by a scalarCombine scalar multiples of matrices10B Linear operations on matrices: Determine whether an inverse exists and calculate itDecide whether a matrix product is defined and give its orderMultiply matricesEvaluate powers of a square matrixIdentify and construct the identity matrix10C Matrix products, powers and permutations: Construct, apply and invert a permutation matrixFind 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 matrix10D Determinants, inverses and matrix equations: Determine whether an inverse exists and calculate it10D Determinants, inverses and matrix equations: Solve a matrix equationUse matrix multiplication to answer an application questionUse row and column matrices of ones to extract totalsRepresent a network in a matrixIdentify the network a connection matrix describesInterpret connection sums and symmetryCount routes using powers of a connection matrixConstruct and analyse relation matrices