1

I am given an $n \times n$ matrix ${\bf A}$, with the following properties: It's diagonals elements are all $0$'s, it is symmetric, and any element of ${\bf A}$ have value either $0$ or $1$. How do I find $k$th power of ${\bf A}$ given constraint on $k = 3000$ and $n = 3000$?

I was trying out with matrix exponentiation, but it's computation complexity is ${\cal O}(n^3 \log(k))$ which is too high with such constraints.

J.Jack
  • 47
  • 1
    Any symmetric real matrix $A$ is diagonalizable, say as $A=P^{-1}DP$ for a diagonal matrix $D$. You then have that $A^{k} = (P^{-1}DP)^{k} = P^{-1} D^{k} P$. What's more, given $D=\operatorname{diag}(x_1,\ldots,x_n)$, it follows that $D^{k}=\operatorname{diag}(x_1^k,\ldots,x_n^k)$. Google has me believing that the complexity of diagonalization is $O(n^3)$ at worst, with some faster algorithms for symmetric matrices that can get closer to $O(n^2)$. – Joe Wells Oct 15 '18 at 23:43
  • @JoeDub can you tell give link of algorithm which can perform this in O(n^2) ? – J.Jack Oct 16 '18 at 04:26
  • Googling originally, I got the answer from this post https://math.stackexchange.com/a/836200/29084

    But looking at it again, I didn't see the "$3bn^3+$" part before $O(n^2)$.

     – Joe Wells Oct 16 '18 at 17:49
  • I have updated my question. Changed constraint on k from 10^9 to 3000. Can anyone help me out ? – J.Jack Oct 19 '18 at 12:42
  • Joedub's answer still holds. Nothing changes if you lower your bound on $n$ and $k$. Additionally, I am slightly unclear what you are asking. Do you have an actual symmetric $0-1$ matrix, or are you trying to find an algorithm (or the complexity of an algorithm) to do this in general? Whatever your answer, diagonalization is the way to go... – JavaMan Oct 19 '18 at 13:30

0 Answers0