Cycles and matrices
Table of Contents
Intro
Traditional way to analyze graphs, paths, to search loops are recursive traversing algorithms. But here we will try to use matrices. For example, detect existence of loops (or cycles, in other words, I used here both words as equal).
Adjacency matrix
The idea is simple: we draw a square and put 1 in the cross cell if the top/header cell has a path/connection to the row cell:
A | B same Octave/Matlab: which means paths/connections:
--+---+--- A = [0, 0; 1, 0] B -> A
A | 0 | 0 or ..and no others
B | 1 | 0 A = [0 0; 1 0]
Formally:
\begin{aligned} A_{ij} &= 1, &\text{if}\ i \to j\\ &= 0, &\text{else} \end{aligned}
where i is a row, j is a column, but we use "named cells" here. The main diagonal is 0 by
definition.
Product of matrices
Formally it is defined as it is explained here and it is not defined for all cases. But for our case (a square matrix) - it is defined always. A power is the same as with usual integers:
n
A = A * ... * A
: :
:--n times--:
Path of a length N
And now the first interesting "pattern":
- \(A^2_{ij}\) - the number of paths of length 2 from
itojnode - \(A^3_{ij}\) - the number of paths of length 3 from
itojnode - \(A^n_{ij}\) - the number of paths of length n from
itojnode - ...
Examples:
Graph A: A -> B B -> C B -> D D -> E E -> C
We can write the path A -> B as A-B or shorter: AB.
Lets check reachability of nodes for 2, 3, 4 steps (for 1 - is the initial adjacency matrix)
with A matrix:
A = [0 1 0 0 0; 0 0 1 1 0; 0 0 0 0 0; 0 0 0 0 1; 0 0 1 0 0] disp("A² (2 stp): AC: AB BC | AD: AB BD | BE: BD DE | DC: DE EC"); A^2 disp("A³ (3 stp): AE: AB BD DE | BC: BD DE EC"); A^3 disp("A⁴ (4 stp): AC: AB BD DE EC"); A^4
A = 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 A² (2 stp): AC: AB BC | AD: AB BD | BE: BD DE | DC: DE EC ans = 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 A³ (3 stp): AE: AB BD DE | BC: BD DE EC ans = 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A⁴ (4 stp): AC: AB BD DE EC ans = 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
How is this pattern explained?
- A power is the multiplication of a matrix by itself.
- The matrix cells at the top (columns) are named the same as those at the side (rows) - these are the same graph nodes. It means the matrix is square.
Considering a 3-nodes graph (A, B, C nodes) we get a 3x3 adjacency matrix. I call it "A"
too, but from the context you will get where a node is, where - a matrix. We will assume that
we have not loops on nodes (no connections of a node with itself, so I marked a main diagonal
with 0 - no connections there, and it follows the definition of the adjacency
matrix).
Notation: A row and B column gives us a cell marked as x in the power example. It is a
connection of B node with A node. If there is a path (it's vector, order matters) B -> A
then here we have 1. Else: 0. I use notation AB for a cell A row, B column. So, x cell
can be designated as AB. Following the rule of multiplication:
M A T R I X:
"A"
A B C
-+------ P O W E R:
A|0 · ·
B|· 0 ·
C|· · 0 x = AB = AB*AA + BB*AB + CB*AC = CB*AC
|| ||
A B C 0 0
-+------
"A"→ A|0 · · y = CB = CA*AB + CB*BB + CC*CB = CA*AB
↓ B|· 0 · || ||
G R A P H: C|· · 0 0 0
A B C
-+------ -+------
A A|0 · · |· x ·
/ \ B|· 0 · |· · · ← A²=A*A
/ \ C|· · 0 |· y ·
B-----C
We agreed to ignore loops on nodes themselves, so AA, BB, CC cells have 0, so
the value in the cell AB in the resulting matrix of A*A is CB*AC (other monomials are 0)
or AC*CB - it is the same, right?
So, we see: AB = AC * CB as a result. How to treat it? Number of path of length 2 (power=2)
from A to B. Look at the graph: the vector rule of a triangle -
\[ \overrightarrow{AB} = \overrightarrow{AC} + \overrightarrow{CB} \]
Bingo: it is exactly the number of 2-step paths from A to B - if there is a 1-step path
from A to C, AC is 1. If there is 1-step path from C to B, then CB is 1. The 2-step
path from A to B is 1 * 1 = 1. But if any of these 2 1-step paths is missing then the
final multiplication will be 0 (zero 2-steps paths from A to B). The multiplication here
works as logical "AND": it's a line of segments and to pass it from the start to the end - all
segments have to be solid, but "0" means a gap on some of segments - think about it in this way:
o---o------o---o 1 * 1 * 1 o---o o---o 1 * 0 * 1
OK, you can check y cell (or CB) in the same manner.
The same with 4-nodes graph - it is more interesting because we will see a sum:
M A T R I X:
"A"
A B C D
-+------- P O W E R:
A|0 · · ·
B|· 0 · ·
C|· · 0 · x = AC = AA*AC + AB*BC + AC*CC + AD*DC = AB*BC + AD*DC
D|· · · 0 || ||
A B C D 0 0
-+-------
"A"→ A|0 · · ·
↓ B|· 0 · ·
G R A P H: C|· · 0 ·
D|· · · 0
A A B C D
/|\ -+------- -+-------
/ | \ A|0 · · · |· · x ·
D | B B|· 0 · · |· · · · ← A²=A*A
\ | / C|· · 0 · |· · · ·
\|/ D|· · · 0 |· · · ·
C
So, the number of 2-step paths AC is a sum of 2 1-step paths AB, BC and the
second/alternative 2-step path from A to C: AD, DC. So, the sum comes from the second -
alternative path! The same idea is for 3-step paths, etc.
The standard multiplication (there are other "multiplication" operations defined for matrices) of matrix is defined in such a way that it corresponds to vectors formed from nodes...
We assumed the case when no any loops on nodes. So, adjacency matrix had 0 in Aₗₗ (if to
return to our notation: in AA, BB, CC, DD, etc - are "0"). When we raise to a power
N, we consider paths of length N, and we can have "1" from some node to itself but not
directly, i.e., indirectly, transitively: \(A^{k}_{ii}\) counts closed walks of length k
starting and ending at node i.
Let's check it with a matrix having a cycle:
Matrix B:
<-----5 steps---->
A -> B AB, BC, CE, ED, DA
A -> C | |
B -> C `-----cycle-----'
C -> E
E -> D
D -> A
B = [0 1 1 0 0; 0 0 1 0 0; 0 0 0 0 1; 1 0 0 0 0; 0 0 0 1 0] disp("B² (2 stp): no loops - no 1 on main diagonal"); B^2 disp("B³ (3 stp): no loops - no 1 on main diagonal"); B^3 disp("B⁴ (4 stp): 4 loops - (A): AC,CE,ED,DA | (C): CE,ED,DA,AC"); disp(" (D): DA,AC,CE,ED | (E): ED,DA,AC,CE") B^4
B =
0 1 1 0 0
0 0 1 0 0
0 0 0 0 1
1 0 0 0 0
0 0 0 1 0
B² (2 stp): no loops - no 1 on main diagonal
ans =
0 0 1 0 1
0 0 0 0 1
0 0 0 1 0
0 1 1 0 0
1 0 0 0 0
B³ (3 stp): no loops - no 1 on main diagonal
ans =
0 0 0 1 1
0 0 0 1 0
1 0 0 0 0
0 0 1 0 1
0 1 1 0 0
B⁴ (4 stp): 4 loops - (A): AC,CE,ED,DA | (C): CE,ED,DA,AC
(D): DA,AC,CE,ED | (E): ED,DA,AC,CE
ans =
1 0 0 1 0
1 0 0 0 0
0 1 1 0 0
0 0 0 1 1
0 0 1 0 1
Pay attention: we cannot find the paths leading to loops using matrix power! I wrote the paths only because I knew it from the beginning: I drew such graph with such loop. Examples, how to determine paths leading to cycles see Detect dependency cycles
But the power operation allows us to determine that there are 4-step loops (power=4) on nodes
A, C, D, E (no on the node B: BB = 0). And using this property, you can:
- build adjacency matrix.
- then to iterate for
Nsteps raising it in a power1, 2, ...Nand if you found "1" on the main diagonal, then this node has a loop. If no one, no loops of 1..N-steps.
Nilpotent matrices and cycles
Nilpotent matrix is a square matrix N such that \(N^k = 0\) (where k > 0, 0 - is a zero
matrix). We have 2 5x5 matrices: A (without cycles, we call it DAG) and B - with cycles.
A directed graph is acyclic (a DAG) iff its adjacency matrix is nilpotent: \(A^n = 0\), where
n is the number of nodes (aka, vertices), i.e.:
\[ A^n \neq 0 \Rightarrow \text{cycle} \]
Let's demonstrate it (nnz() is the number of non 0 elements):
A = [0 1 0 0 0; 0 0 1 1 0; 0 0 0 0 0; 0 0 0 0 1; 0 0 1 0 0] C = A^5 disp("Is A a nilpotent matrix (DAG)? "); nnz(C) == 0 B = [0 1 1 0 0; 0 0 1 0 0; 0 0 0 0 1; 1 0 0 0 0; 0 0 0 1 0] C = B^5 disp("Is B a nilpotent matrix (DAG)? "); nnz(C) == 0
A = 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 C = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Is A a nilpotent matrix (DAG)? ans = 1 B = 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 C = 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 Is B a nilpotent matrix (DAG)? ans = 0
Yes, B is not DAG (contains loops). Why do we raise to the power n, equal to the number of
vertices? The number of edges is n - 1 if a graph does not have cycles - because every 1
segment needs 2 points:
A A A A / \ / \ / \ / \ / \ / \ B C B-----C B-----C B-----C 3 nodes 3 nodes 3 nodes 3 nodes 2 edges 2 edges 2 edges 3 edges
but if edges/links are n, then we have a loop. So, loops begin from n number of edges, and
to catch even one, we check the minimum power - n:
| Length | What can happen? |
|---|---|
| ≤ n-1 | A walk may visit every vertex once, with no repetition. |
| n | A repeated vertex is guaranteed. |
| > n | More repetitions are unavoidable. |
Eigenvalues of matrix and cycles
For any labeling of a DAG, the adjacency matrix has only the eigenvalues 0. We can use a
function eig() to find eigenvalues:
A = [0 1 0 0 0; 0 0 1 1 0; 0 0 0 0 0; 0 0 0 0 1; 0 0 1 0 0] B = [0 1 1 0 0; 0 0 1 0 0; 0 0 0 0 1; 1 0 0 0 0; 0 0 0 1 0] disp("Eigenvalue of A:"); C=eig(A) disp("Is A a DAG?"); nnz(C) == 0 disp("Eigenvalue of B:"); C=eig(B) disp("Is B a DAG?"); nnz(C) == 0
A = 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 B = 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 Eigenvalue of A: C = 0 0 0 0 0 Is A a DAG? ans = 1 Eigenvalue of B: C = 1.1673 + 0i 0.1812 + 1.0840i 0.1812 - 1.0840i -0.7649 + 0.3525i -0.7649 - 0.3525i Is B a DAG? ans = 0
So, using eigenvalue of a matrix, we also can detect a cycle/cycles: A has not cycles (it is
a DAG) - all 5 eigenvalues are 0, but B is not a DAG (it has cycles). C (5 eigenvalues)
contains complex numbers due to a solution of a corresponding quadratic equation.
Conclusion
Matrix based methods allow to determine when a graph has a cycle (or cycles) but these methods have drastically worse performance than traversal algorithms on graphs that additionally to it - report a path leading to the cycle.