5
\$\begingroup\$

Problem 1 - Matrix powers in R

R does not have a built-in command for taking matrix powers.

Write a function matrixpower() with two arguments mat and k that will take integer powers k of a matrix mat.

My attempted solution.

matrixMul <- function(mat1, mat2)
{
    rows <- nrow(mat1)
    cols <- ncol(mat2)

    if(rows == cols)
    {
        matOut <- matrix(nrow = rows, ncol = cols) # empty matrix

        for (i in 1:rows) 
        {
            for(j in 1:cols)
            {
                vec1 <- mat1[i,]
                vec2 <- mat2[,j]

                mult1 <- vec1 * vec2

                matOut[i,j] <- sum(mult1)
            }
        }

        return(matOut)
    }
    else
    {
        return (matrix( rep( 0, len=25), nrow = 5))
    }
}


matrixpower<-function(mat1, k)
{
    pow1 <- abs(k)

    rows <- nrow(mat1)
    cols <- ncol(mat1)

    matOut <- diag(1, rows, cols)

    if(pow1 == 0)
    {
        return(matout)
    }
    if (pow1 == 1)
    {
        matOut <- mat1 
    }

    if(pow1 > 1)
    {
        for (i in 1:pow1) 
        {
            matOut <- matrixMul(matOut, mat1)
        }
    }

    if(k < 0)
    {
        matOut <- solve(matOut)
    }

    return (matOut) 
}

mat1 <- matrix(c(1,2,3,4), nrow = 2, ncol=2)
pow1 <- matrixpower(mat1, -2)
pow1 

I have a few questions here.

  1. Is there any room for improvement in this code?
  2. Does this problem ask for manual implementation of multiplication? Or, should the use of %*% suffice?
\$\endgroup\$
  • 1
    \$\begingroup\$ In case you're more interested in the result than in the exercise of writing the function yourself, check out matrixcalc::matrix.power() or stats.stackexchange.com/questions/4320/… \$\endgroup\$ – hplieninger Apr 25 at 6:42
  • \$\begingroup\$ I think you can assume that the matrix multiplication operator is allowed in your solution. \$\endgroup\$ – Russ Hyde Apr 25 at 12:16
  • \$\begingroup\$ Not the fastest solution (would be what Jorge suggested) but a good candidate for the use of a recursion. \$\endgroup\$ – flodel Apr 25 at 23:48
4
\$\begingroup\$

It would be more efficient to use binary exponentiation.

Suppose that you want to raise an n by n matrix to the \$k^{th}\$ power.

The current method requires that you do a normal matrix multiplication \$k-1\$ times.

This of course has complexity \$k\$ multiplied by \$f(n)\$, Where \$f(n)\$ is the complexity of a matrix multiplication ( This is usually \$n^ 3\$ unless you write some fancy shmancy code that no one writes)

If you use binary exponentiation you reduce the number of multiplications to \$log(k)\$. Specifically the number of multiplications is the ceiling of \$log_2(k)\$ plus the number of 1 bits in the binary representation of \$k\$.

This is of course much more efficient for large values of \$k\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.