Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a directed graph $G$, and let $A$ be $G$'s adjacency matrix, whose $(i,j)$-entry is 1 when there is an edge from $i$ to $j$. Is there any interpretative meaning of the $(i,j)$-entry of the matrix $(A^5\cdot{(A^T)}^5)$ and the matrix $({(A^T)}^8\cdot{A}^8)$, respectively ?

share|improve this question
    
Sorry, I've refined the question. –  John Smith Oct 7 '12 at 13:31

1 Answer 1

up vote 4 down vote accepted

The intuition comes easily if you stop thinking of the matrix elements as switches for the edges. Instead, think of $(A)_{ij}$ as the number of distinct walks of length $1$ from $i$ to $j$. Try! ;)

Note this also allows you to account naturally for looping, directed, undirected and multiple edges if you don't restrict to a symmetric matrix with null diagonal and elements in $\{0,1\}$.

What happens if you take a power of the adjacency matrix? Multiplying the matrices you are essentially concatenating walks, so...

$(A^k)_{ij}$ is the number of distinct walks of length $k$ from $i$ to $j$.

Transposing the matrix simply flips the edges. So..

$((A^T)^kA^l)_{ij}$ is the number of distinct walks of length $k+l$ starting from $i$, doing $k$ steps against the direction of the edges and $l$ steps following them finally arriving at $j$. The meaning of $(A^k(A^T)^l)_{ij}$ is similar.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.