Proving two matrices are mutually inverse using pictures

Aditya Khanna

(joint work with N. Loehr)

​

Graduate Online Combinatorics Colloquium

Uncut and uncensored version

We start with matrices

We start with combinatorial matrices

A matrix is called combinatorial if its entries can be computed as a weighted sum of objects.

A matrix is called combinatorial if its entries can be computed as a weighted sum of objects.

We start with combinatorial matrices

Pascal matrices

0 1 2 3 4

0

1

2

3

4

Pascal matrices

Combinatorial

Matrix

Pascal matrix*

*truncated

Combinatorial

Matrix

Pascal matrix*

*truncated

Combinatorial

Matrix

Pascal matrix*

*truncated

Kostka matrices

To understand this matrix combinatorially, we need a bit of background.

Compositions and Partitions

A weakly decreasing composition is called a partition.

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Young Tableau

Checkpoint!

questions?!

covered till now: combinatorial matrices, compositions/partitions, semi-standard Young tableau

Kostka matrix counts SSYTs

Kostka matrix counts SSYTs

Kostka matrix counts SSYTs

Symmetric functions

but didn’t you say matrices were maps? What is the Kostka matrix mapping between?

Symmetric functions

but didn’t you say matrices were maps? What is the Kostka matrix mapping between?

Symmetric functions

Symmetric functions

Symmetric functions

Schur functions

For each SSYT, we can find a content monomial

shape

content

​

content monomial

Schur functions

with a small caveat that contents now are compositions that might contain zeroes

Schur functions

No problem!

Schur functions

Schur functions

Schur functions

Schur functions

Schur functions

Schur functions

Kostka numbers algebraically

there is a way to understand this as a map between basis using non-commutative symmetric functions

Checkpoint!

questions?!

Kostka matrix recursion???

Kostka matrix recursion???

Kostka matrix recursion???

Kostka matrix recursion???

Kosta matrix recursion

Kosta matrix recursion

Combinatorial matrix recursion

Combinatorial matrix recursion

Combinatorial matrix recursion

Combinatorial matrix recursion

signed weight

Recursion on object level

We saw that the recursion for matrices arises by removing cells with the largest filling.

This actually gives us a recipe to construct objects step-by-step.

SSYTs and horizontal strips

What do we notice about the highlighted cells?

They don’t share columns! A horizontal strip is a collection of cells with no two cells in the same column

SSYTs and horizontal strips

An SSYT can be built up using horizontal strips

Inverse of the Kostka matrix

A matrix needs a friend, and so we consider the right inverse of the Kostka matrix.

this justifies the redundant columns of our Kostka matrix

Special ribbons

ribbon

Special ribbons

ribbon

also known as a rim-hook or a border-strip

Special ribbons

ribbon

special ribbon

(starts in first column)

Special ribbons

ribbon

special ribbon

Special ribbons

ribbon

special ribbon

Special ribbon tableau

Let us now add the special ribbons step-by-step

Special ribbon tableau

Let us now add the special ribbons step-by-step

Special ribbon tableau

Let us now add the special ribbons step-by-step

Special ribbon tableau

Let us now add the special ribbons step-by-step

Back to the matrices

Fact [trust me]

There is at most one SRT of given shape and content.

This identity holds using matrix multiplication

BUT CAN WE SHOW IT USING PICTURES?

Checkpoint!

questions?!

covered till now: Kostka matrix recursion, general recursion, SSYTs with horizontal strips, special ribbon tableaux, inverse Kostka matrix

The problem in context

Theorem (Kostka case)

if and only if

remove H

add S

special ribbon of size L

horizontal strip of size L

A single row is a horizontal strip as well as a special ribbon.

remove H

add S

special ribbon of size L

horizontal strip of size L

Ribbons really want to climb up a column, but horizontal strips hate it.

Exactly as the theorem wanted!

remove H

add S

special ribbon of size L

horizontal strip of size L

remove H

add S

special ribbon of size L

horizontal strip of size L

EXACTLY�ONE �MORE!

remove H

add S

special ribbon of size L

horizontal strip of size L

this cell is called the head of S

The involution

If head of S intersects with H, we “push down” the special-rim hook by one row

If head of S is disjoint with H, we “push up” the special-rim hook by one row

remove H

add S

special ribbon of size L

horizontal strip of size L

The involution

If head of S intersects with H,

we “push down” the special-rim hook by one row

If head of S is disjoint with H,

we “push up” the special-rim hook by one row

Exactly as the theorem wanted!

remove H

add S

special ribbon of size L

horizontal strip of size L

The involution

If head of S intersects with H,

we “push down” the special-rim hook by one row

If head of S is disjoint with H,

we “push up” the special-rim hook by one row

General theorem statement

if and only if

remove

add

Global bijection

We have an equivalent condition for mutual inverses but what is actually happening to the objects?

“signed weighted sums over some objects”

Global bijection

Sign-reversing involution

Fixed point

Canonical Kostka bijection

SSYT

SRT

Canonical Kostka bijection

SSYT

SRT

Canonical Kostka bijection

SSYT

SRT

remember this?

Canonical Kostka bijection

SSYT

SRT

These two pairs of SSYT and SRT have opposite signs!

Yay for bijections

Let’s talk about some other applications of this that we cover in the paper.

Ribbon tableaux

The above involution is an ingredient in proving that the characters of a symmetric group are orthogonal.

Composition diagrams

proves Mobius inversion (inclusion-exclusion) for the lattice of sets

Brick tabloids

Would take too long to describe, but they show that the cancelling is not always due to an involution.

Check out our paper!

(soon to appear in EJC)

• We improve upon celebrated bijections by providing shorter and canonical proofs.
• We also show results pertaining to quasisymmetric and noncommutative symmetric function matrices.
• 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

Thank you for listening!

Scan for an Arxiv link to the paper!

any questions?

please fill out the feedback form!

Algebraic Combinatorics

symbols

pictures

Combinatorics

Polynomials

is a vector space with basis elements

Change-of-basis

?

Change-of-basis

Transition Matrix

Symmetric Functions

Compositions and Partitions

A weakly decreasing composition is called a partition.

A weakly decreasing composition is called a partition.

Compositions and Partitions

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

Abstract

Algebraic combinatorics studies the interplay of algebra (e.g. polynomials, vector spaces) and combinatorics (pictures). The entries of some matrices between vector spaces can be computed by counting certain signed, weighted objects. In this talk, we will explore how one can prove that matrices are inverses using local manipulations on certain diagrams. We will illustrate this idea using the refinement matrix R on compositions. The proof that RR^{-1} = I reduces to removing and adding boxes in a diagram.

There are no prerequisites for this talk, and all algebraic and combinatorial concepts will be defined in the talk.