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?
By replacing $M$ with $M^{T}$, we can work with columns rather than rows, so let us assume we want to find the first column of $M^k$. Let $v$ be the vector $v = (1,0, \cdots, 0)$, so that $M^{k}v$ gives the first column of $M^{k}$. We can then compute $M^{k}v = M(M(M(\cdots Mv)))$, i.e. through $k$ matrix-vector multiplications. Each multiplication has complexity $O(N^2)$, so we get $O(N^2k)$.
In principle, you can also try decomposing $v$ into eigenvectors of $M$ (if $M$ is diagonalizable), in which case computing $M^kv$ is very fast. However, the complexity of finding an eigendecomposition seems to be of the same order as the original problem, so this won't help much.