I am well aware that if $A$ is the adjacency matrix of a graph, then $A^n=a^{(n)}_{ij}$ counts the number of walks of length $n$ from vertex $i$ to vertex $j$. Is there a way to modify this so that you end up with a matrix that counts the paths between vertices?
For me a path is a walk that doesn't repeat vertices.
This would also have interesting consequences as being able to count the number of n-cycles in a graph, etc.
Has anyone thought of this before? I haven't been able to find literature concerning this.
Here's what I've thought so far, I'm trying to do it recursively:
Start with $A$, the adjacency matrix of a graph. Then $a_{ij}$ is the number of paths of length 1 from vertex $i$ to vertex $j$. Notice there aren't any walks that aren't paths.
Multiply by $A$ to get $A^2$. The only walks that aren't paths are on the diagonal (these are walks of the type $v_i v_j v_i$). We get rid of them by considering $A^2-diag(A^2)$. Here $diag(A^2)$ means leaving the diagonal as it is and making every off-diagonal entry $0$ (don't know if there's standard notation fot that).
Multiply by $A$ to get $A(A^2-diag(A^2))$. Now, this matrix counts how many walks there are between two vertices that start with a path of lentgh 2. That means we have paths of the type $v_i v_j v_k v_j$ which we don´t want to count. Notice that for each path of lentgh one (let's say the edge $v_i v_j$) we have $deg(v_j)-1$ paths that we don't want. Therefore, we have to subtract $A\circ B$ where $B$ is the matrix defined by $b_{ij}=deg(v_j)-1$ and $\circ$ is the Hadamard product (pointwise product).
Finally, $A(A^2-diag(A^2))-A\circ B$ gives us the number of paths from a vertex to the other.
Following this idea I conjectured that in general, if $\tilde{A_n}$ is the matrix that counts paths of length $n$, then $$\tilde{A_n} = A(\tilde{A_{n-1}})-(A^{n-2}-diag(A^{n-2}))\circ B$$
Edit: This is not correct as pointed out in the answer.
Note that if $A$ has $n-1$ vertices, then ${\overline A}_{n-1}=0$, but your conjectured formula doesn't give ${\overline A}_n=0$.