Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A Bijective Proof of Borchardt’s Identity. | A Bijective Proof of Borchardt s Identity Dan Singer Minnesota State University Mankato Submitted Jul 28 2003 Accepted Jul 5 2004 Published Jul 26 2004 Abstract We prove Borchardt s identity det xi - VjJ per xi - Vj e - Vj 2 by means of sign-reversing involutions. Keywords Borchardt s identity determinant permanent sign-reversing involution alternating sign matrix. MR Subject Code 05A99 1 Introduction In this paper we present a bijective proof of Borchardt s identity one which relies only on rearranging terms in a sum by means of sign-reversing involutions. The proof reveals interesting properties of pairs of permutations. We will first give a brief history of this identity indicating methods of proof. The permanent of a square matrix is the sum of its diagonal products n per aij n 1 Ơ Sn i 1 where Sn denotes the symmetric group on n letters. In 1855 Borchardt proved the following identity which expresses the product of the determinant and the permanent of a certain matrix as a determinant 1 Theorem . M j x--yj THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R48 1 Borchardt proved this identity algebraically using Lagrange s interpolation formula. In 1859 Cayley proved a generalization of this formula for 3 X 3 matrices 4 Theorem . Let A aij be a 3 X 3 matrix with non-zero entries and let B and C be 3 X 3 matrices whose i j entries are a2j and a-1 respectively. Then det A per A det B 2 i aj j det C . i j When the matrix A in this identity is equal to xi yj -1 the matrix C is of rank no greater than 2 and has determinant equal to zero. Cayley s proof involved rearranging the terms of the product det A per A . In 1920 Muir gave a general formula for the product of a determinant and a permanent 8 Theorem . Let P and Q be n X n matrices. Then det P per Q e a det Pơ Q XX where Pơ is the matrix whose ith row is the ơ i th row of P Pơ Q is the Hadamard product and e ơ denotes the sign of Ơ. Muir s proof also involved a simple rearranging of .
