Timeline for What is the n-th power of the adjacency matrix equal to?

6 events

when toggle format	what		by	license	comment
Jun 27, 2011 at 17:30	comment	added	David Harris		This doesn't work. This would give a polynomial-time algorithm for Hamiltonian path (i.e. a cycle-free path from $a$ to $b$ of length exactly $n$) but that is NP-complete.
Jun 13, 2011 at 16:54	comment	added	Aaron Meyerowitz		If you define $P_n$ to be the matrix whose $u,v$ entry is $t$ if the minimum distance from $u$ to $v$ is $n$ and there are $t$ minimal walks of that length, then $P_{n+1}=(P_nA)$ if instead you let $(\cdot)^$ mean zero out everything which was non-zero for any $m \le n$.
May 16, 2011 at 9:22	comment	added	Mark Meilstrup		@Qiauchu - I never claimed it was efficient, although in my opinion it is 'simple'. But then I realized it doesn't completely work - see edit.
May 16, 2011 at 9:20	history	edited	Mark Meilstrup	CC BY-SA 3.0	added 243 characters in body
May 16, 2011 at 9:15	comment	added	Qiaochu Yuan		Note that as Johan indicates in the comments this is much less efficient than taking powers of a matrix, since you can't use binary exponentiation: you really have to multiply (and modify the diagonal) $n$ times.
May 16, 2011 at 9:05	history	answered	Mark Meilstrup	CC BY-SA 3.0