7
$\begingroup$

The adjacency matrix I have at the start is

[0,1,0,0,0]
[0,0,1,0,0]
[1,0,0,1,1]
[0,0,0,0,0]
[0,0,0,0,0]

I don't understand why this matrix^9999 equals

[1,0,0,1,1]
[0,1,0,0,0]
[0,0,1,0,0]
[0,0,0,0,0]
[0,0,0,0,0]

or why this matrix^33334 equals
[0,1,0,0,0]
[0,0,1,0,0]
[1,0,0,1,1]
[0,0,0,0,0]
[0,0,0,0,0]

Can someone please explain what is happening?

Improve this question
$\endgroup$
2
  • $\begingroup$ By Frobenius normal form of your adjacency matrix, the isomorphic of your graph is digraph G { 2 -> 1 2 -> 4 3 -> 2 4 -> 3 } $\endgroup$
    – Amin235
    Commented Dec 12, 2016 at 8:39
  • $\begingroup$ I would have migrated this to Math.SE, except that it's too old to migrate. $\endgroup$
    – Todd Trimble
    Commented May 17, 2017 at 12:37

2 Answers 2

Reset to default
6
$\begingroup$

Vertex $1$ is connected to $2,$ $2$ to $3,$ $3$ to $1, 4, 5,$ and $4$ and $5$ have no out edges, so your graph is a directed cycle with a couple of hairs pointing out. The number of paths of length $k$ from $1$ to $2$ is $1$ if $k = 1 \mod 3,$ and $0$ otherwise. same from $2$ to $3,$ same from $3$ to $1.$ Similarly for paths from $1$ to $3,$(except $k$ has to be $2 \mod 3$), etc.

Improve this answer
$\endgroup$
5
$\begingroup$

Since the adjacency matrix $\mathrm A$ is not symmetric, we have a directed graph.

enter image description here

Given a positive integer $k$, the $(i,j)$-th entry of $\mathrm A^k$ gives us the number of directed walks of length $k$ from $i$ to $j$. Given the cycle $1 \to 2 \to 3 \to 1$, the entry $(\mathrm A^k)_{11}$ should be $1$ when $k$ is a multiple of $3$ and $0$ when $k$ is not a multiple of $3$. Using SymPy, we can verify this:

>>> A = Matrix([[0,1,0,0,0],
                [0,0,1,0,0],
                [1,0,0,1,1],
                [0,0,0,0,0],
                [0,0,0,0,0]])
>>> A**2
[0  0  1  0  0]
[             ]
[1  0  0  1  1]
[             ]
[0  1  0  0  0]
[             ]
[0  0  0  0  0]
[             ]
[0  0  0  0  0]
>>> A**3
[1  0  0  1  1]
[             ]
[0  1  0  0  0]
[             ]
[0  0  1  0  0]
[             ]
[0  0  0  0  0]
[             ]
[0  0  0  0  0]
>>> A**4
[0  1  0  0  0]
[             ]
[0  0  1  0  0]
[             ]
[1  0  0  1  1]
[             ]
[0  0  0  0  0]
[             ]
[0  0  0  0  0]
>>> A**5
[0  0  1  0  0]
[             ]
[1  0  0  1  1]
[             ]
[0  1  0  0  0]
[             ]
[0  0  0  0  0]
[             ]
[0  0  0  0  0]
>>> A**6
[1  0  0  1  1]
[             ]
[0  1  0  0  0]
[             ]
[0  0  1  0  0]
[             ]
[0  0  0  0  0]
[             ]
[0  0  0  0  0]

Note that $9999$ is a multiple of $3$, whereas $33334$ is not.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Digraph generated with webgraphviz.com digraph G { 1 -> 2 2 -> 3 3 -> 1 3 -> 4 3 -> 5 } $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 12, 2016 at 0:08

Not the answer you're looking for? Browse other questions tagged .