# A general linear combination for linearly dependent matrices

Let $n$ be a natural number and $m=n^2+1$.

I would like to prove the following:

There exist polynomials $p_1,...,p_{m}$ with integer coefficients whose variables are of the form $x_{i,j,k}$, $1\leq i\leq m$ and $1\leq j,k\leq n$, such that the following holds:
If $A_1,\ldots,A_m$ are matrices of integers of size $n\times n$ then $p_1(\bar{A}) A_1 + \cdots + p_{m}(\bar{A}) A_{m}=0$, where $p_s(\bar{A})$ denotes the result of evaluating each of the variables $x_{i,j,k}$ in $p_s$ to the entry $(j,k)$ of $A_i$, and not all of the evaluated values $p_t(\bar{A})$ are zero.

Obviously the matrices are linearly dependent since $m>n^2$, so they have some linear combination with a non-zero coefficient. I think it should also be true that there is this general linear combination which treats the entries of the matrices as variables and which can be evaluated to get the linear combination for each specific choice of $A_1,\ldots,A_m$, but I am not sure how to prove it.

Any ideas?

-
I would try the case $n=1$, $m=2$ first. –  1015 Mar 8 '13 at 14:20

Formulating this in terms of matrices is a distracting complication. Consider the $n^2$-dimensional vector space of $n\times n$ matrices and ignore their matrix structure. More generally, $d+1$ vectors $v_i$ in $\mathbb R^d$ are linearly dependent, and a vanishing linear combination is given by the determinant
$$\left| \matrix{ v_{11}&v_{12}&\cdots&v_{1d}&v_1\\ v_{21}&v_{22}&\cdots&v_{2d}&v_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ v_{d+1,1}&v_{d+1,2}&\cdots&v_{d+1,d}&v_{d+1} } \right| \;.$$
I confess I don't understand how this answers the question and gives the polynomials $p_j$. It might be too early... Could you expand a little bit? –  1015 Mar 8 '13 at 14:58
@julien: The determinant is a linear combination of the $v_i$, and the coefficients are subdeterminants, and thus polynomials in the vector components. Thus applying this with $d=n\times n$ and arranging the vectors as matrices yields an answer to the question. The only part it doesn't address is that the coefficients will all be $0$ if the rank isn't maximal. I suspect that it's impossible to make the coefficients polynomials and always non-zero; if I can come up with a proof for that I'll add it. –  joriki Mar 8 '13 at 16:20
@julien: Actually I'd overlooked the requirement that the coefficients be integers, but fortunately they are; they're all $\pm1$. –  joriki Mar 8 '13 at 16:34
Since determinants are computed in (commutative) rings, I think a more proper (though longer) description would be as follows. Take the above determinant with indeterminates $X_i$ instead of the $v_i$ in the final columns, which is homogeneous of total degree$~1$: $c_1X_1+\cdots+c_{d+1}X_{d+1}$. Now setting $X_i:=f(v_i)$ for all $i\leq d+1$ and any coordinate function $f:\Bbb R^d\to\Bbb R$ (or more generally any linear form$~f$) makes this expression vanish by anti-linearity of the determinant, so $c_1v_1+\cdots c_{d+1}v_{d+1}\in\Bbb R^d$ must be zero. –  Marc van Leeuwen Sep 30 '13 at 12:26