MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What is J? What is this sign reversing involution supposed to be more general than? – Qiaochu Yuan Jul 26 '10 at 7:20
Sorry it should be K. – Alex Jul 26 '10 at 7:25
I know, I know... I was merely trying to show by example that the question could use some rewriting! – Mariano Suárez-Alvarez Jul 26 '10 at 7:38
@Qiaochu: Here is the paper by Sagan and Lee… – Alex Jul 26 '10 at 7:44
Alex, please edit the relevant information in the text of the question itself. That way, it is mch more easy to see what is being asked. – Mariano Suárez-Alvarez Jul 26 '10 at 8:10

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.