Kostka Matrix Identity

Question

How does one prove $K^{-1}K = I$ using a more general sign reversing involution, where $K$ is the Kostka matrix and $I$ is the identity matrix?

Answer 1

As I imagine you already know, Egecioglu and Remmel gave an elegant bijective proof that $K K^{-1}=I$. And, as you say, Sagan and Lee gave a bijective proof that $K^{-1} K = I$, but it is much more complicated. I imagine this is the proof you want to improve.

One of the surprising facts about bijective proofs is that sometimes there is an elegant proof for $AB=I$ but not for $BA=I$. I use "elegant" in a vague sense, because Loehr and Mendes have an algorithm which takes a bijective proof of $AB=I$ and outputs a bijective proof of $BA=I$, so there are no examples where there is a bijective proof of one equality and not the other. Loehr and Mendes work out the bijection proving $K^{-1} K=I$ as one of their examples.

Since Loehr and Mendes is the only paper in MathSciNet citing Sagan and Lee, and there are no papers citing Loehr and Mendes, I'm going to guess that there has not been further progress on this subject. Hopefully Richard Stanley, Igor Pak or Ira Gessel will turn up soon; if they haven't heard about any progress, it will be extremely safe to guess that there hasn't been any.

It occurs to me that it might be interesting to try to show, in the sense of computational complexity, that there are situations where there is a short bijective proof of $AB=I$ but only long bijective proofs for $BA=I$. Speaking vaguely, the obstacle should be that the implication $(AB=I) \implies (BA=I)$, although true in the $n \times n$ matrices for any $n$, is not true in an arbitrary ring, so you somehow need to know that you are dealing with matrices. I haven't thought about this question in any depth.