Journal of Combinatorics

Volume 10 (2019)

Number 2

Combinatorial proofs of identities involving symmetric matrices

Pages: 243 – 253

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n2.a4

Author

Samantha Dahlberg (Department of Mathematics, University of British Columbia, Vancouver, B.C., Canada)

Abstract

Brualdi and Ma found a connection between involutions of length $n$ with $k$ descents and symmetric $k \times k$ matrices with non-negative integer entries summing to $n$ and having no row or column of zeros. From their main theorem they derived two alternating sums by algebraic means and asked for combinatorial proofs. In this note we provide such demonstrations making use of the Robinson–Schensted–Knuth correspondence between symmetric matrices and semi-standard Young Tableau. Additionally, we restate the proof of Brualdi and Ma’s main result with this perspective which shortens the argument.

Keywords

involutions, descents, symmetric matrices, RSK, standard Young Tableau, semi-standard Young Tableau

2010 Mathematics Subject Classification

Primary 05A05. Secondary 05A17, 05A19.

Received 10 August 2017

Published 25 January 2019