Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of $P(X_1, X_2, ..., X_M)$ is nilpotent?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ How about binary exponentiation? Are you expecting an answer that doesn’t just use an algorithm that checks whether a matrix is nilpotent? $\endgroup$– Qiaochu YuanCommented Sep 11, 2020 at 0:22
-
$\begingroup$ I'm looking for anything that behaves better than the straight-forward computation of the polynomial. Preferably something involving as few matrix multiplications as possible (even fewer than what binary exponentiation uses). I am unsure if such an algorithm exists. $\endgroup$– Andrei ComanCommented Sep 11, 2020 at 1:29
Add a comment
|