Post History
#2: Post edited
by
trichoplax
·
2023-05-29T10:38:34Z (over 1 year ago)
Tidying
Finding a single row of Matrix after exponentiation
- 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 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 entire matrix?
- 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?
#1: Initial revision
by
theabbie
·
2023-05-28T16:42:22Z (over 1 year ago)
Finding a single row of Matrix after exponentiation
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 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 entire matrix?