%larcombe.tex: a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger
%On Invariance Properties of Entries of Matrix Powers
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf On Invariance Properties of Entries of Matrix Powers}
\bigskip
\centerline
{\it Shalosh B. EKHAD and Doron ZEILBERGER}
\bigskip
{\bf Abstract}: A few years ago, Peter Larcombe discovered an amazing property regarding two by two matrices. For any such $2 \times 2$ matrix $A$,
the ratios of the two anti-diagonal entries is the same for all powers of $A$.
We discuss extensions to higher dimensions, and give a short bijective proof of Larcombe and Eric Fennessey's elegant extension
to tri-diagonal matrices of {\it arbitrary} dimension. This article is accompanied by a Maple package.
{\bf Peter Larcombe's Surprising Discovery}
In [2], Peter Larcombe gave four proofs of a seemingly new and amazing property of a $2 \times 2$ matrix, for any such matrix
(we denote the $(i,j)$ entry of a matrix $B$ by $B_{ij}$)
$$
A_{12} \cdot (A^m)_{21}=A_{21} \cdot (A^m)_{12} \quad,
$$
for {\it all} positive integers $m$.
We first observe that, in hindsight (but only in hindsight!) this is not that surprising. More generally, for a general $n \times n$ matrix $A$,
and any subset $S$ of cardinality $n+1$
of the set of $n^2$ entries $\{(i,j) \,|\, 1\leq i,j \leq n\}$, there exist polynomials $q_s(A)$ in the entries of $A$ (independent of $m$) such that
$$
\sum_{s \in S} \, q_s \cdot (A^m)_s \, = \, 0 \quad,
\eqno(1)
$$
for all $m>1$.
This fact follows from the {\bf Cayley-Hamilton} equation that says that
If $P_A(x):=\det(A-x\,I)$ is the {\bf characteristic polynomial} of $A$, then the $n \times n$ matrix $P_A(A)$ equals the {\bf zero matrix} ${\bf 0}$ . Writing
$$
P_A(x)=\sum_{k=0}^{n} p_k x^k \quad ,
$$
we have
$$
\sum_{k=0}^{n} p_k A^k= {\bf 0} \quad,
$$
where ${\bf 0}$ is the all-zero matrix.
Multiplying by $A^m$ we get
$$
\sum_{k=0}^{n} p_k A^{m+k} = {\bf 0} \quad,
$$
for all $m$.
Taking the $ij$ entry, we have that each of the $n^2$ sequences $(A^m)_{ij}$ satisfy the {\bf same} $n^{th}$-order linear recurrence equation with {\bf constant coefficients}
$$
\sum_{k=0}^{n} p_k (A^{m+k})_{ij} = 0 \quad .
$$
It is well-known and easy to see ([1][8]) that any $n+1$ sequences that satisfy the {\bf same} recurrence of order $n$, must be {\bf linearly dependent}.
Also, in order to find the relation, it is enough to find $n+1$ values of the $q_s$ for which $(1)$ holds for the $m \,= \, 1, \, 2, \dots, n$. Then this linear combination
also satisfies that very same linear recurrence, and since it {\bf vanishes} at the first $n$ {\bf initial conditions} it must be {\bf identically zero}.
If our subset $S$ of entries only consists of non-diagonal entries, we can do even better, Eq. $(1)$ is true for any set $S$ of $n$ non-diagonal entries.
Note that the Cayley-Hamilton equation implies that
$$
\sum_{k=1}^{n} p_k A^k \quad
$$
is a {\bf diagonal} matrix (namely $-\det(A) \bf I$), hence for a non-diagonal entry $ij$ ($i \neq j$), $(A^m)_{ij}$ always satisfies the {\bf same} linear recurrence equation (with constant coefficients)
of order $n-1$, hence any $n$ such non-diagonal entries must be {\bf linearly dependent}. In the original case of a $2 \times 2$ matrix discussed in [2], it follows that the $(1,2)$ and $(2,1)$ entries of $A^m$
always satisfy the {\bf same} relation as those of $A$, hence we have yet-another-proof (without equations!) of Larcombe's amazing discovery.
But what about higher dimensions? Now things get much more complicated, and we need a computer algebra system (in our case Maple). For example, we have the
following
{\bf Theorem}: Let $A=(a_{ij})_{1\leq i,j\leq 3}$ be a $3 \times 3$ matrix, then for {\bf all} $m \geq 1$, we have
$$
\left(a_{12} a_{21} a_{23}-a_{13} a_{21} a_{22}+a_{13} a_{21} a_{33}-a_{13} a_{23} a_{31}\right) \cdot (A^m)_{12}
$$
$$
+\left(a_{12} a_{23} a_{31}-a_{13} a_{21} a_{32}\right) \cdot (A^m)_{13}
$$
$$
+\left(-a_{12}^{2} a_{23}+a_{12} a_{13} a_{22}-a_{12} a_{13} a_{33}+a_{13}^{2} a_{32}\right) \cdot (A^m)_{21} \,=\, 0 \quad .
$$
There are three more such theorems (up to trivial isomorphism) for the $n=3$ case, while
there are $27$ inequivalent cases for $n=4$. They can all be found in the following output file
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oLarcombe1.txt} \quad .
We were unable to find the corresponding relations for $n=5$, they got too complicated!
\vfill\eject
{\bf A bijective proof of the Larcombe-Fennessey theorem about Tridiagonal matrices}
Any matrix identity for a fixed dimension is essentially {\it high-school algebra} and can be verified by a computer algebra system, even if the power $m$ is arbitrary. But the following theorem
of Larcombe and Fennessey, regarding {\bf tridiagonal} matrices of {\it arbitrary} dimension is {\it university algebra} and is more interesting.
{\bf Theorem} (Larcombe and Fennessey [3][6]) : Let $A$ be a general $n \times n$ tridiagonal matrix (for {\it any} $n \geq 2$), then for all $1 \leq i i$ satisfy $v - u > 1$.
(That is, there is a "tridiagonal bottleneck" between $i$ and $i+1$ in
$A$.) Your proof still applies to this generalization, except that the
words should not be "continuous" but rather need to pass the $(i,i+1)$ checkpoint whenever they cross the border between "$\leq i$" and
"$> i$". Instead of continuity, you thus need to make a "what goes up
must come down" argument when constructing the bijection.
{\bf Acknowledgment}: Many thanks are due to Peter Larcombe, the referee, and Darij Grinberg for very helpful remarks on a previous version.
{\bf References}
[1] Manuel Kauers and Peter Paule, {\it ``The Concrete Tetrahedron''}, Springer, 2011.
[2] P. J. Larcombe, {\it A note on the invariance of the general $2 \times 2$ matrix anti-diagonal ratio with increasing matrix powers: four proofs},
Fib. Quarterly {\bf 53}, 360-364 (2015).
[3] P. J. Larcombe and E. J. Fennessey, {\it A new tri-diagonal matrix invariance property}, Palest. J. Math. {\bf 7}, 9-13 (2018).
[4] P. J. Larcombe and E. J. Fennessey, {\it A note on two rational invariants for a particular $2 \times 2$ matrix}, Palest. J. Math. {\bf 7}, 410-413 (2018).
[5] P. J. Larcombe and E. J. Fennessey, {\it On anti-diagonals ratio invariance with exponentiation of a $2 \times 2$ matrix: two new proofs}, Palest. J. Math. {\bf 9}, 12-14 (2020).
[6] P. J. Larcombe and E. J. Fennessey,
{\it A formalised inductive approach to establish the invariance of antidiagonal ratios with exponentiation for a tri-diagonal matrix of fixed dimension},
Palest. J. Math. {\bf 9}, 670-672 (2020).
[7] P. J. Larcombe and E. J. Fennessey,
{\it A short graph-theoretic proof of the $2 \times 2$ matrix anti-diagonal ratio invariance with exponentiation}, Palest. J. Math. {\bf 10}, 102-103 (2021).
[8] Doron Zeilberger, {\it The C-finite Ansatz}, Ramanujan Journal {\bf 31} (2013), 23-32.\hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/cfinite.html} \quad .
\bigskip
\hrule
\bigskip
Shalosh B. Ekhad and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt [ShaloshBEkhad, DoronZeil] at gmail dot com} \quad .
First Written: {\bf July 27, 2021}. This version: {\bf Aug. 4, 2021}.
\end