I've got an $n\times n$ matrix that is upper-triangular (all zeros below diagonal), diagonal entries are positive, and entries that are not on the diagonal are either $0$ or $1$. An example matrix looks like this. $$A=\begin{pmatrix} 69 & 0 & 1 & 1 & 0 \\ 0 & 100 & 1 & 0 & 1 \\ 0 & 0 & 15 & 0 & 1 \\ 0 & 0 & 0 & 15 & 1 \\ 0 & 0 & 0 & 0 & 300 \end{pmatrix}$$ I'm interested in the upper-right entry of a large power (say $A^k$) of this matrix with computations done in a finite field $\mathbb{F}_p$ for some fixed prime $p$. Is it possible to compute this faster than usual for this kind of matrices? I'm looking for runtimes something similar to $O(n^2)$ preprocessing and $O(n\lg k)$ per query.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Do you mean for a given $A$ and $p$ you want to compute the upper right entries for many different $k$? Then it may make sense to precompute the Jordan normal form (of course the eigenvalues are the diagonal entries).. $\endgroup$– Robert IsraelCommented Apr 7, 2020 at 16:28
-
$\begingroup$ @RobertIsrael: yes for the first question. But wouldn't computing the Jordan normal form end up taking at least $O(n^3)$ precomputation time (given the eigenvalues, I still would need to compute several kernels)? That's unfortunately too much for my purpose. $\endgroup$– Donald GyllenhalCommented Apr 8, 2020 at 2:19
-
$\begingroup$ Your matrix structure doesn't seem particularly special. How can you expect time linear in $n$ when the size of the output is $\Theta(n^2)$? $\endgroup$– Brendan McKayCommented Apr 8, 2020 at 6:21
-
1$\begingroup$ You’re computing in a finite field, so when you say the diagonal entries are positive, do you just mean nonzero? $\endgroup$– Zach TeitlerCommented Apr 9, 2020 at 1:10
-
2$\begingroup$ I mean they are nonzero modulo $p$. Sorry for the confusion. $\endgroup$– Donald GyllenhalCommented Apr 9, 2020 at 5:35
|
Show 2 more comments