# How to read off coefficients of tensor-like expression in a speedy way?

I am considering identities involving t[a, b, c, d, ...], where number of indices is fixed. t has the cyclic property so that t[3, 4, 1, 2] is equal to t[1, 2, 3, 4].

When $k=4$, all possible elements are generated by

basis = (# /. {List -> t}) & /@ Permutations[Range[4]];
basis = basis /. {t[a___, 1, b___] -> t[1, b, a]} // Union


Here comes the output:

{t[1, 2, 3, 4], t[1, 2, 4, 3], t[1, 3, 2, 4], t[1, 3, 4, 2], t[1, 4, 2, 3], t[1, 4, 3, 2]}


I want to convert expressions like t[1, 2, 3, 4] + t[1, 3, 2, 4] - t[1, 4, 3, 2] into a coefficient matrix to do some linear algebra. I tried the following code:

identity = {t[1, 2, 3, 4] + t[1, 3, 2, 4] - t[1, 4, 3, 2],
t[1, 2, 4, 3] + t[1, 3, 2, 4],
t[1, 3, 4, 2] - t[1, 2, 3, 4] - t[1, 4, 2, 3]};

coeffmatrix = Coefficient[identity, #] & /@ basis // Transpose


The output is

{{1, 0, 1, 0, 0, -1}, {0, 1, 1, 0, 0, 0}, {-1, 0, 0, 1, -1, 0}}.


Efficiency does not matter for this small example. However, when I increase number of indices and identities, getting coeffmatrix becomes very slow and spends a huge amount of memory. For the real case, t has 10 indices and the size of coeffmatrix is approximately $362880 \times 362880$.

Here comes my question: Coefficients are always restricted to {-1, 0, 1} for some reasons. Would this fact probably help me to boost up the performance? Could anyone give me a suggestion for better efficiency?

-
Would using a SparseArray help? –  Tobias Hagge Apr 10 '13 at 0:58
@TobiasHagge I am not familiar with SparseArray. What is the benefit to use SparseArray? –  Joonho Kim Apr 10 '13 at 1:06
more efficient storage and faster computations on matrices for which most of the coefficients are zero. –  Tobias Hagge Apr 10 '13 at 4:56
@TobiasHagge Is it possible to calculate the matrix rank directly from SparseArray? –  Joonho Kim Apr 10 '13 at 5:47
I haven't used sparse arrays much, but my understanding is that most of mathematica's linear algebra functions are implemented to transparently work with them. CoefficientArrays, by the way, produces a SparseArray, so if you want to test performance you can compute the rank using the matrices computed by both your algorithm and Mr. Wizard's, and see which is faster. –  Tobias Hagge Apr 10 '13 at 15:29

CoefficientArrays[identity, basis][[2]] // MatrixForm

$\left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 0 & -1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & -1 & 0 \end{array} \right)$
Amazing! It's about 100 times faster than before. Can we do the same linear algebra with SparseArray? –  Joonho Kim Apr 10 '13 at 1:21