Singular matrix geometric sum What is a fast way to calculate the sum
$M + M^2+M^3+M^4+\cdots+M^n$,
where $M$ is an $n \times n$ matrix whose cells are either $0$ or $1$?
I have researched an alternative way which makes use of the fact that $I+M+M^2+\cdots+M^n=(I-M)^{-1}(I-M^{n+1})$, however singular matrices are not welcome in this method plus it requires $M$'s eigenvalues to be less than $1$ in absolute value.
Is there a smarter way to calculate it than performing $M(I+M(I+M(I+M(\cdots(I +M (I)))))$, i.e. less computationally expensive? Alas, eigenvalues are not known beforehand.
 A: Let $g_n(x) = x + x^2+x^3+x^4+\cdots+x^n$ and define $f_n(x) = 1+g_n(x)$. Then clearly, computing $f_n$ is just as hard as computing $g_n$.
Now observe that
$$f_{2n+1}(x) = 1+x+\dots+x^{2n+1}=(1+x)(1+x^2+\dots+x^{2n}) = (1+x)f_n(x^2), $$
to obtain the recursive algorithm given by:
$$ \begin{cases} f_{2n+1}(x) &=  (1+x)f_n(x^2) \\ f_{2n}(x) &= f_{2n-1}(x) + x^{2n} \\ f_1(x) &= 1+x \\ f_0(x)&=1. \end{cases} $$
I believe that this will require roughly $O(\log n)$ operations, if addition and multiplication require $O(1)$ operations. To evaluate it on a matrix argument, use exponentiation by squaring to evaluate the $x^{2n}$. 
Finally note that for fixed $n$, this expansion may be precomputed and possibly further optimized. The key observations used here were that
\begin{aligned} f_{nm}(x) &= \frac{x^{mn}-1}{x-1} = \frac{x^{mn}-1}{x^m-1}\frac{x^{m}-1}{x-1} = f_n(x^m) f_m(x) \\
 f_{a+b}(x) &= f_a(x) + x^{a+1} f_{b-1}(x), \end{aligned}
here applied with $m=2$ and $b=1$, although variants apply to compute $f_n$ for any (composite) number $n$. 
A: My purpose is the following. I'd like to use that we are in $\mathbb{F}_2$, so $1+x^2 = (1+x)^2$.
$$ 1 + x + x^2 + x^3 + \dots + x^n = (1+x)^2 + x(1+x)^2 + \dots = (1+x)^2(1+x+\dots x^{n-2})$$ so we can go on in this method and get $$ \sum_0^{n}x^k=(1+x)^{n}$$ 
Concluding you get that 
$$ M\sum_0^{n-1}M^k=M(I+M)^{n-1}$$ 
If $M$ is diagonalizable that's just $0$.
