The nth power of a matrix C programming

Question

anonymous · Answer

This is the program for multiplying matrix A(nxn) 2 times:

void product(int a[][20],int c[][20],int n)
{
   for(i=0;i<n;i++)
   {
        for(j=0;j<n;j++)
        {
             c[i][j]=0;
             for(k=0;k<n;k++)
             {
                  c[i][j]+=a[k][j]*b[i][k];
             }
         }
      }
}
Modify this code to multiply the A matrix n times!!!

anonymous · Answer

@UnkleRhaukus @dan815 @robtobey @wio @chmvijay @ikram002p @Faman39 @danish071996

e.mccormick · Answer

What did you do so far?  Where did you have trouble?

anonymous · Answer

Think about the memory of your matrices.

If you only have a single matrix, then putting it into product once will result in that matrix being squared.  If you put it a second time, you are now multiplying it with its square, which is equivalent to finding the 4th power. $(A^2)^2 = A^4$.

anonymous · Answer

So what you want to do is create a copy of the matrix.  You need to multiply it with it's copy multiple times.  If you do the product once, you will get $A^1\cdot A^1 = A^2$.  If you do the product n times, you will get $A^1 \underbrace{\cdot A^1\cdot \ldots \cdot A^1}_n= A^{n+1}$.  So you want to multiply it with it's copy n-1 times.

anonymous · Answer

However, consider if $n=8$.  We would this would take $7$ multiplications.
But if we did $((A^2)^2)^2 = A^8$, it would only take $3$ multiplications.
So if $n$ is a very large power of $2$, we could potentially save time by computing squares consecutively.

anonymous · Answer

Now if it were something like $n=9$, then we can calculate for $A^8$ using squaring method, and then multiply that with $A^1$.  This would be 4 multiplications instead of 8.

anonymous · Answer

If we had something like $A^{100}$, we could convert this to $A^{64}\cdot A^{32}\cdot A^{4}$, because $64+32+4 = 100$, and because $A^{2^6}\cdot A^{2^5}\cdot A^{2^2}$ meaning that it would take 6 multiplications to get $A^{64}$, in the process we would have found $A^{32}$ and $A^4$, and then 2 more multiplications to multiply them all together.  That results in $8$ multiplications by using squaring, instead of $99$ multiplications by using a straight forward approach.

queelius · Answer

wio, this is a fairly importance optimization you speak of, and it is very simple to express recursively:

Matrix power(Matrix m, unsigned int n)
{
    if (n == 0)
        return Matrix::Identity(m.size());
    else if (n % 2 == 0) // if n is even
        return power(m, n / 2) * power(m, n / 2);
    else // if (n % 2 != 0)
        return m * power(m, n - 1);
}

So, instead of n multiplications, you will only need ceiling(log(n)) multiplications.

queelius · Answer

Oops, sorry, I used C++ syntax.