Nilpotent Matrices

[Dragonfall]

Given an nxn matrix, how do I know whether it's nilpotent?

[trambolin]

Compute the eigenvalues and check if they are all zero.

[Dragonfall]

Why is it that when you have 30 15x15 matrices, it is impossible to find out whether some chain of them will multiply out to be 0?

[Hurkyl]

I wonder if it's easier to just compute powers of the matrix to decide if it's nilpotent?


Anyways, for your new question, that sounds like a variant on the word problem (http://en.wikipedia.org/wiki/Word_problem_for_groups). The direct translation of the word problem into matrices would be to tell if a product of some given matrices gives you the identity -- I have no idea if using zero instead makes a difference.

[trambolin]

well a quick and dirty solution would be checking the rank of each and every matrix and remove the invertible chains. Then you can concentrate on the nullspace vectors of those remaining. I know it really doesn't sound nice.

Singular value decomposition should be doable for 30 of them in a row.

[Hurkyl]

You can't eliminate the invertible ones. Consider the following set of 2x2 matrices:


\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)
\qquad \qquad
\left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right)


There is a product of these matrices that gives zero... but it requires use of the invertible matrix.

[Dragonfall]

Damn. If I were given something like this to work on for my thesis, and it turns out to be undecidable, that'll suck.

[trambolin]

You can't eliminate the invertible ones. Consider the following set of 2x2 matrices:


\left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)
\qquad \qquad
\left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right)


There is a product of these matrices that gives zero... but it requires use of the invertible matrix.

No it is not zero. Again after obtaining the nullspace vectors you can reduce the number of conditions to check...

[Hurkyl]

If you name the first matrix A and the second B, then ABAB is zero.

[trambolin]

I did not understand that you meant multiple products of the same matrices.

But, that is exactly what I am saying. Because a column of A is in the kernel of B. Instead of checking ABAB...AB you can check if the columns of product of the invertible ones are in the nullspace of the singular ones. If not whatever happens the product is nonzero.

Note that I said it is just a dirty way of doing it.