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\$
3
  • 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\$ Apr 25, 2019 at 6:42
  • \$\begingroup\$ I think you can assume that the matrix multiplication operator is allowed in your solution. \$\endgroup\$
    – Russ Hyde
    Apr 25, 2019 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, 2019 at 23:48

1 Answer 1

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\$
5
  • \$\begingroup\$ Welcome to Code! Can you edit your answer to give an explanation of why binary exponentiation would be more efficient? If there is documentation that supports this claim then feel free to cite any such sources. \$\endgroup\$ Apr 25, 2019 at 4:35
  • 2
    \$\begingroup\$ Done !!!!!!!!!!!! \$\endgroup\$
    – user62030
    Apr 25, 2019 at 4:40
  • \$\begingroup\$ Thanks for showing me how to use math mode ! \$\endgroup\$
    – user62030
    Apr 25, 2019 at 5:18
  • 1
    \$\begingroup\$ yeah - for more info see the LaTeX section of the formatting page. \$\endgroup\$ Apr 25, 2019 at 5:20
  • \$\begingroup\$ See stackoverflow.com/a/40901360/1201032 for a simple implementation. \$\endgroup\$
    – flodel
    Apr 25, 2019 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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