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.

Assume that I have a large, non-symmetric matrix $\bf{A}$ of zeros and ones. If I want the exact diagonal elements of $\bf{A}^{k}$ (not the trace, but the elements themselves) where $k$ is some large whole number, I can

  1. Multiply the matrices out using with exact integers, possibly speeding the computation by using some Addition-chain exponentiation.

  2. Diagonalize the matrix as $\bf A = V \Gamma V^{-1}$ and compute $\bf A^{k} = V \Gamma^{k} V^{-1}$

The first method is slow but accurate, while the second method can introduce numerical errors (since the exact answer is required). Is there some decomposition I am missing that does what I'm looking for?

share|improve this question
2  
What is larger, $k$ or the size of the matrix? If it is $k$, you could use the Cayley-Hamilton theorem for computing the diagonal entries of every power of $A$ once you know those of the first $n$ powers of $A$ (where $n$ is the size of $A$). –  darij grinberg Feb 18 '11 at 18:47
    
Both cases are needed - though I never thought that the Cayley-Hamilton theorem could be used like that, it's brilliant! It doesn't however help when $k$ is less then the size of the matrix. –  Hooked Feb 18 '11 at 19:11

1 Answer 1

up vote 5 down vote accepted

(edit : this is for large k, so it may not be useful for k comparable to n)

A faster way to compute high powers of a matrix is by computing in the $\mathbb{Z}$-algebra $\mathbb{Z}[M]$. The space $(I_n,M,M^2, \ldots)$ is a subspace of $M_n(\mathbb{Z})$, and in fact the Cayley-Hamilton theorem tells you that it has dimension at most $n$. For example, sometimes, the $n$ coefficients on the diagonal of the matrix (or the the coefficients on the first row, or column, etc) are enough to know what the rest of the coefficients are.

If $P$ is the minimal polynomial of $M$ over $\mathbb{Z}$ and has degree $d = d_P$, the basis the best suited in order to compute products, however, is the basis $(1,M,\ldots M^{d-1})$ : we want to use the isomorphism $\mathbb{Z}[M] = \mathbb{Z}[X]/P$. Doing one multiplication in there requires $O(d^2)$ operations :

Keep a table of the coordinates of $(1,M,\ldots M^{2d-2})$ in the basis $(1,M,\ldots M^{d-1})$, then compute the coefficients $c_k$ in $$ (\Sigma_{i=0}^{d-1} a_i M^i)(\Sigma_{j=0}^{d-1} b_j M^j) = \Sigma_{k=0}^{2d-2} (c_k = \Sigma_{i+j=k} a_i b_j) M^k$$ Then use that table to convert this sum into a vector $\Sigma_{k=0}^{d-1} d_k M^k$.

You can further optimize this algorithm if the polynomial $P$ is reducible. If $P = QR$ with $Q$ and $R$ having no factor in common, then $\mathbb{Z}[M] = \mathbb{Z}[X]/P \simeq \mathbb{Z}[X]/Q \times \mathbb{Z}[X]/R$. The isomorphism here sends $X$ onto the pair $X,X$. you will need to compute the inverse of the isomorphism, but once you do that, you gain in complexity because $d_Q^2 + d_R^2 < (d_Q + d_R)^2 = d_P^2$.

You can also improve if you have $P = Q^k$ for some $k$, because then, $\mathbb{Z}[X]/P \simeq \mathbb{Z}[X,Y]/(Q(X),Y^k)$, where the isomorphism sends $X$ onto $X+Y$. Once again, the computations there are shorter since you have $k$ polynomials of degree $d/k$ to compute, it will take $O(k(d/k)^2 = O(d^2/k)$.

You have to compute $P$, its factorization, and the isomorphisms only once. Once you have done all this preliminary work you get a very good algorithm. If the matrix is diagonalizable (in $M_n(\mathbb{Z})$), you will get that $P$ factors completely into distincts factors of degree 1, and this will give you an algorithm equivalent to the one you gave.

Even if you don't want to factorize $P$, simply working in $\mathbb{Z}[X]/P$ gives a good optimisation. You can compute $P$ by taking some element $x$ in $\mathbb{Z}^n$, and checking when $M^k x$ becomes linearly dependant on $1, x, \ldots x^{k-1}$. If you are lucky you get some dependancy for $k<n$, which means you have found a factor of $P$ of degree $k<n$. If you know of any subspace of $\mathbb{Z}^n$ stable by $M$, be sure to make use of it, picking $x$ in it will give you such a factor of $P$.

share|improve this answer
    
this is great, I'll have to read into this quite a bit more. Can you suggest an entry level reference (that hopefully provides an example)? –  Hooked Feb 18 '11 at 21:02

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.