Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

Finding a single row of Matrix after exponentiation

+5
−0

Suppose I have a matrix $M$ of $N \times N$ and I only want a single row of this matrix after raising it to power $K$ ie. some row of $M ^ K$.

This can be done in $O(N^3 \log K)$ at best (or better using advanced matrix multiplication techniques) if we find the entire matrix. However, I am only interested in finding one row of this resultant matrix.

Would it be possible to find one particular row more efficiently than finding the entire matrix?

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+2
−0

While there are no doubt even more clever things you can do, the most straightforward approach, which will likely make a significant improvement, is to move from matrix-matrix multiplication to matrix-vector multiplication.

Let $e_k$ be a (column) vector with all $0$s except the $k$-th entry is $1$. To get the $k$-th row of a matrix, you just multiply it on the right by $e_k^T$, i.e. $e_k^T M$. Then, instead of computing $e_k^T (M^K)$, you compute $(\cdots((e_k^T M)M)\cdots M)$. You won't be able to exploit repeated squaring, but this takes $O(KN^2)$ time, so if $K < N$ this is faster than doing even a single matrix-matrix multiplication. If $K > N$, you can square $M$ to halve $K$ and quickly get $K < N$. You can do some simple algebra to figure out how many squarings are worthwhile. However, when $K$ is much greater than $N$, you may be better off doing diagonalization-based techniques. If your matrix is diagonalizable (e.g. if it is positive definite), then there are algorithms to diagonalize in $O(N^3)$ time. Once you have the diagonalized form, exponentiation is just exponentiating the components of the diagonal matrix. You would then have something like $O(N^3 + N\log K)$. There are very many techniques to do better at this problem if your matrix has some known special structure.

History
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »