On Invariance Properties of Entries of Matrix Powers

Shalosh B. EKHAD and Doron ZEILBERGER

Abstract: A few years ago, Peter Larcombe discovered an amazing property regarding two by two matrices. For any such 2 × 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 arbitrary dimension. This article is accompanied by a Maple package.

Peter Larcombe’s Surprising Discovery

In [2], Peter Larcombe gave four proofs of a seemingly new and amazing property of a 2×2 matrix, for any such matrix (we denote the (i, j) entry of a matrix B by B_{ij})

A_{12} · (A^{m})_{21} = A_{21} · (A^{m})_{12} ,

for 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×n matrix A, and any subset S of cardinality n+1 of the set of n^{2} entries {(i, j) | 1 ≤ i, j ≤ n}, there exist polynomials q_{s}(A) in the entries of A (independent of m) such that

∑_{s∈S} q_{s} · (A^{m})_{s} = 0 ,  (1)

for all m > 1.

This fact follows from the Cayley-Hamilton equation that says that If P_{A}(x) := det(A − x I) is the characteristic polynomial of A, then the n × n matrix P_{A}(A) equals the zero matrix 0 . Writing

P_{A}(x) = ∑_{k=0}^{n} p_{k}x^{k} ,

we have

∑_{k=0}^{n} p_{k}A^{k} = 0 ,

where 0 is the all-zero matrix. Multiplying by A^{m} we get

∑_{k=0}^{n} p_{k}A^{m+k} = 0 ,

for all m.

Taking the ij entry, we have that each of the n^{2} sequences (A^{m})_{ij} satisfy the same n^{th}-order linear recurrence equation with constant coefficients

∑_{k=0}^{n} p_{k}(A^{m+k})_{ij} = 0 .

It is well-known and easy to see ([1][8]) that any n + 1 sequences that satisfy the same recurrence of order n, must be 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, …, n. Then this linear combination also satisfies that very same linear recurrence, and since it vanishes at the first n initial conditions it must be 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

∑_{k=1}^{n} p_{k}A^{k}

is a diagonal matrix (namely − det(A)I), hence for a non-diagonal entry ij (i ≠ j), (A^{m})_{ij} always satisfies the same linear recurrence equation (with constant coefficients) of order n − 1, hence any n such non-diagonal entries must be linearly dependent. In the original case of a 2 × 2 matrix discussed in [2], it follows that the (1, 2) and (2, 1) entries of A^{m} always satisfy the 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

Theorem: Let A = (a_{ij})_{1≤i,j≤3} be a 3 × 3 matrix, then for all m ≥ 1, we have

(a_{12}a_{21}a_{23} − a_{13}a_{21}a_{22} + a_{13}a_{21}a_{33} − a_{13}a_{23}a_{31}) · (A^{m})_{12}
+ (a_{12}a_{23}a_{31} − a_{13}a_{21}a_{32}) · (A^{m})_{13}
+ (−a_{12}^{2}a_{23} + a_{12}a_{13}a_{22} − a_{12}a_{13}a_{33} + a_{13}^{2}a_{32}) · (A^{m})_{21} = 0 .

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

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oLarcombe1.txt .

We were unable to find the corresponding relations for n = 5, they got too complicated!

A bijective proof of the Larcombe-Fennessey theorem about Tridiagonal matrices

Any matrix identity for a fixed dimension is essentially 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 tridiagonal matrices of arbitrary dimension is university algebra and is more interesting.

Theorem (Larcombe and Fennessey [3][6]) : Let A be a general n × n tridiagonal matrix (for any n ≥ 2), then for all 1 ≤ i < n, and all m ≥ 1, we have

a_{i,i+1} · (A^{m})_{i+1,i} = a_{i+1,i} · (A^{m})_{i,i+1} .  (2)

For a concrete example see [3].

We will give a combinatorial proof. Fix n and let a_{i,j} (1 ≤ i, j ≤ n) be n^{2} commuting indeterminates. It follows immediately from the definition of matrix multiplication that the (i, j) entry of A^{m} is the weight-enumerator of the set of (m + 1)-letter words in the alphabet {1, 2, …, n} whose first letter is i and last letter is j, with the weight

W eight(w_{1} … w_{m+1}) := a_{w_{1} w_{2}} · a_{w_{2} w_{3}} ⋯ a_{w_{m−1} w_{m}} · a_{w_{m} w_{m+1}} .

For example W eight(123123) = a_{12}a_{23}a_{31}a_{12}a_{23}.

If our matrix is tridiagonal, then all the words are continuous i.e. after the letter i can only come one of the (up to) three letters {i − 1, i, i + 1}. For example if n = 5 then the following is a legal word

2333234333221122112234455443 ,

but the following one is not

233312 ,

because after the fourth letter, that is a ‘3’, comes the letter ‘1’.

Let W_{m}(i, j) be the set of legal (m+1)-letter words in the alphabet {1, 2, …, n} that start with the letter i and end with the letter j. Its weight-enumerator (i.e. sum of the weights of its members) is (A^{m})_{ij}, where now A is a generic n × n tridiagonal matrix. For ease of type-setting let i′ := i + 1.

Note that:

• The left side of (2) is the weight-enumerator of the set of words, i W_{m}(i′, i), which is the set of legal (m + 2)-letter words that start and end with the letter i, and whose second letter is i′.

• The right side of (2) is is the weight-enumerator of i′ W_{m}(i, i′) which is the set of legal (m + 2)- letter words that start and end with the letter i′, and whose second letter if i.

We claim that The mapping

T_{i} : i W_{m}(i′, i) → i′ W_{m}(i, i′) ,

to be defined next, is a weight-preserving bijection. Let w = w_{1}w_{2} … w_{m+2} be a member of i W_{m}(i′, i), then of course w_{1} = i and w_{2} = i′, and w_{m+2} = i. Let k be the smallest index such that w_{k} = i′, w_{k+1} = i. Of course it exists (by “continuity”). Case I: k = 2. If m = 1 then the word must be i i′i and we map it to i′ i i′. Otherwise we can write

w = i i′ i u i ,

for some (m − 2)-letter word u, and we define

T_{i}(w) := i′ i u i i′ ,

that of course belongs to i′ W_{m}(i, i′). Case II: k = m + 1, then we can write

w = i i′ u i′ i ,

for some (m − 2)-letter word u, and we map it to the

T_{i}(w) := i′ i i′ u i′ ,

that of course belongs to i′ W_{m}(i, i′). Case III: 2 < k < m + 1. Then we can write

w = i i′ u i′ i v i ,

for some words u and v, whose total length is m − 2, and we define T_{i}(w) := i′ i v i i′ u i′ , that of course belongs to i′ W_{m}(i, i′). Let’s state the inverse mapping

U_{i} : i′ W_{m}(i, i′) → i W_{m}(i′, i) .

Let w = w_{1}w_{2} … w_{m+2} be a member of i′ W_{m}(i, i′), then of course w_{1} = i′ and w_{2} = i, and w_{m+2} = i′. Let k be the largest index such that w_{k} = i, w_{k+1} = i′. Of course it exists (by “continuity”). Case I: k = m + 1. If m = 2 the w = i′ i i′ and we let U_{i}(w) be i i′ i. Otherwise we can write

w = i′ i u i i′ ,

for some (m − 2)-letter word u, and we define

U_{i}(w) := i i′ i u i .

Case II: k = 2. We can write

w = i′ i i′ u i′

and we define

U_{i}(w) := i i′ u i′ i .

Case III: 2 < k < m + 1. We can write

w = i′ i v i i′ u i′ ,

for some words u and v whose lengths add-up to m − 2, and we define

U_{i}(w) := i i′ u i′ i v i .

Readers are welcome to play with the Maple package

https://sites.math.rutgers.edu/~zeilberg/tokhniot/Larcombe.txt ,

that contains procedure REL to discover generalized Larcombe relations (mentioned above) and also implements the above bijection (procedures Ti and Ui, and CheckTi verifies it empirically). In order to use the Maple package, one should have Maple, of course. Then start a Maple session, and type read `Larcombe.txt`. For on-line help, type

ezra(); .

Darij Grinberg’s Extension Darij Grinberg discovered that our argument proves a bit more. Here is what he wrote to us: I’d like to remark that (2) holds not only if A is tridiagonal, but more generally if A has the property that (*) a_{u,v} = a_{v,u} = 0 whenever u ≤ i and v > 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 ”≤ i” and ”> i”. Instead of continuity, you thus need to make a ”what goes up must come down” argument when constructing the bijection. Acknowledgment: Many thanks are due to Peter Larcombe, the referee, and Darij Grinberg for very helpful remarks on a previous version. References

[1] Manuel Kauers and Peter Paule, “The Concrete Tetrahedron”, Springer, 2011.

[2] P. J. Larcombe, A note on the invariance of the general 2 × 2 matrix anti-diagonal ratio with increasing matrix powers: four proofs, Fib. Quarterly 53, 360-364 (2015).

[3] P. J. Larcombe and E. J. Fennessey, A new tri-diagonal matrix invariance property, Palest. J. Math. 7, 9-13 (2018).

[4] P. J. Larcombe and E. J. Fennessey, A note on two rational invariants for a particular 2 × 2 matrix, Palest. J. Math. 7, 410-413 (2018).

[5] P. J. Larcombe and E. J. Fennessey, On anti-diagonals ratio invariance with exponentiation of a 2 × 2 matrix: two new proofs, Palest. J. Math. 9, 12-14 (2020).

[6] P. J. Larcombe and E. J. Fennessey, A formalised inductive approach to establish the invariance of antidiagonal ratios with exponentiation for a tri-diagonal matrix of fixed dimension, Palest. J. Math. 9, 670-672 (2020).

[7] P. J. Larcombe and E. J. Fennessey, A short graph-theoretic proof of the 2×2 matrix anti-diagonal ratio invariance with exponentiation, Palest. J. Math. 10, 102-103 (2021).

[8] Doron Zeilberger, The C-finite Ansatz, Ramanujan Journal 31 (2013), 23-32.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cfinite.html .

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.

Email: [ShaloshBEkhad, DoronZeil] at gmail dot com .

First Written: July 27, 2021. This version: Aug. 4, 2021.