Proving two matrices are mutually inverse using pictures

Aditya Khanna

(joint work with N. Loehr)

​

Graduate Online Combinatorics Colloquium

Algebraic Combinatorics

Algebraic Combinatorics

symbols

pictures

Polynomials

is a vector space with basis elements

Change-of-basis

?

Change-of-basis

Combinatorics

Transition Matrix

Symmetric Functions

Compositions

A weakly decreasing composition is called a partition.

Compositions

A weakly decreasing composition is called a partition.

Transition Matrices

Our theorem

Suppose we have two recursively-constructed matrices A and B.

if and only if

remove

add

- L boxes

+ L boxes

Refinement matrix

Mobius inversion

You might have seen Mobius inversion as an operation when the sum is over divisors.

But it can be performed over any ordering. So our matrix inversion is Mobius inversion for the refinement ordering which in the language of sets is the inclusion ordering.

Remove…

If the whole last row is removed, then the sign of is +1

…and add

Same diagrams

remove boxes from last row

add boxes below the diagram

?

Same diagrams

Different diagrams

Different diagrams

Different diagrams

Different diagrams

QED!

remove

add

- L boxes from the last row

+ L boxes below

Other stuff in our preprint

(accepted in EJC!)

We improve upon celebrated bijections by providing shorter and canonical proofs such as the case of the Kostka matrix and orthogonality of characters of the symmetric group.

This technique can be used outside for matrices not arising from symmetric functions, such as the Hadamard matrix.

(joint with N. Loehr) A local framework for proving combinatorial matrix inversion theorems

arxiv:2505.10783