A nilpotent matrix is a square matrix A that has the property that for SOME integer power k, we have A^k is entirely zero. The smallest power to cause it to be entirely zero is called the index. And for a matrix of size nxn, the index k cannot exceed n. As such, it is probably reasonable to just use a simple loop, where each iteration will just mutiply by A. Check for all zeros at each iteration.
Can you get more fancy? Well yes. If the matrix is large, then it is probably efficient to compute some subset of powers of A. Store them away. For a matrix of size nxn, I would guess that an appropriate scheme would have you generate the powers of A from 1 to sqrt(n), saving all of them. If any of those powers were all zero, then you are done. If not, then you can use a variation of a bisection search to find the actual index. (You just need to get tricky. NEVER raise the matrices to a power.)
Is that more efficient than a purely linear search form 1 to n? ONLY if n is quite large would it even matter.
As for using a direct bisection search, that forces you to compute relatively large powers of A at each iteration. And that in itself will not be efficient. For example, consider the random matrix:
n = 2500;
A = rand(n,n); % surely not nilpotent, but who cares as an example?
timeit(@() A*A)
timeit(@() A^1000)
So raising a large matrix to a power is considerably more expensive than a simple matrix multiply. With n = 2500, it looks like you can do roughly 15 simple matrix multiplies for each such power operation. How would you write it as a loop? DON"T USE POWERS!
As a test, we know a tridiagonal matrix with all zeros on the diagonal must be nilpotent.
A = triu(ones(9),1)
nilIndex(A)
This next matrix will surely not be nilpotent.
A = randi(10,[10,10]) - 5
nilIndex(A)
function k = nilIndex(A)
n = size(A,1);
k = NaN;
Apow = A;
for i = 1:n
if ~any(Apow,'all')
k = i;
break
else
Apow = Apow*A;
end
end
if isnan(k)
disp('A is not nilpotent')
end
end
The point is, your bisection scheme is not nearly as efficient as you think it is. Again, a simple loop is surely better than you think. So, unless this was a homework assignment, where you were instructed to use bisection (sigh) or you have the coding chutzpah to code up that scheme I described above, just use a basic loop. An interesting question is what would be the optimal size of the initial linear sample to employ.
