# Evaluating only one column of a $m \times m$ matrix without evaluating the matrix itself

Suppose I have

f[x_] := SparseArray[{someRules}, {m, m}];
g[x_] := MatrixPower[f[x], k];


Would it be possible to evaluate only the $n$-th column ($n\neq m$) of g without evaluating the whole thing?

Would a simple a = g[x'][[n]] work? Or should I define f and g differently?

EDIT: I just noticed I wrote the above expression for a row, not a column, so the correct expression would be a = g[x'][[All, 1]]. Just a defect of form, of course; the problem still is the same.

• a = g[x'][[n]] certainly will not work. It is an interesting question and a difficult problem. I'm inclined to say it is not possible, unless your columns all happen to be linearly independent, but hopefully I will be proved wrong. – Oleksandr R. Sep 23 '15 at 17:10
• @PatrickStevens to form a matrix power requires a matrix decomposition (e.g. SVD), does it not? And this operation depends on the whole matrix, not just one column. I interpret the question as asking how we can avoid doing calculations that affect only values not lying in this column. – Oleksandr R. Sep 23 '15 at 17:13
• Never use N as a variable, since it is a Mathematica function (give numerical value). It is also good practice to avoid all upper-case letters for variables, such as your K. Also do not use upper-case for named terms, such as Rules, since it may conflict with the thousands of Mathematica function names (such as the close Rule). Don't even do it as an "example," as others will cut-and-paste your code. Get into good coding habits! You could very very easily use myRules, n, and k here, no matter how complicated your own terms were. – David G. Stork Sep 23 '15 at 17:18
• Have you tried just working out the indexed form of the product of a matrix K times? That seems like the most straightforward way. Wikipedia even has the sums worked out on the Matrix Multiplication page, you'd just need to translate it to MMA. – N.J.Evans Sep 23 '15 at 17:30
• Based on some simple testing the general result depends on the entire f matrix, so there is no way around that. (Of course if there is some specific structure to the sparse array that might change things ) – george2079 Sep 23 '15 at 18:40

The documentation for MatrixPower[] indicates that you can take the action of a matrix power on a given vector. In particular, to get a single column of a matrix power, you thus need the action of the matrix power on an appropriate unit vector.

For instance,

n = 6;
mat = SparseArray[{{j_, k_} /; j + k == n + 1 :> 1, {k_, k_} :> 1}, {n, n}];

m = 4; (* power *) k = 3; (* column *)
MatrixPower[mat, m, UnitVector[n, k]]
{0, 0, 8, 8, 0, 0}

mp = MatrixPower[mat, m];
mp[[All, k]]
{0, 0, 8, 8, 0, 0}


MatrixExp[] also admits an "action" form.

• I didn't know about this. Does this speed up the process? – Enzo Oct 8 '15 at 11:13
• Assuming that they implemented it properly under the hood, yes. Actions of matrix functions are an active area of research, it should be said. – J. M.'s technical difficulties Oct 8 '15 at 11:29
• Alright. What if now, instead of MatrixPower, I wanted to do multiplications between matrices? They all have the same structure. For example, I'd like to do a := Table[{RandomChoice[{i, j}], ... , RandomChoice[{k, l}]}, {n}] (where a is set delayed) so I'd want the k-th column of b=a.a.a ... .a Is this possible, or should I just take the column, now? – Enzo Oct 11 '15 at 17:01
• I don't know if there's a more efficient way than just multiplying the matrices in sequence to a unit vector. – J. M.'s technical difficulties Oct 11 '15 at 17:28
• 31 hours reduced to just 40 minutes... I'd say that's an improvement! Thank you so much. – Enzo Oct 16 '15 at 9:46