Rook polynomials to and from permanents (Q1869240): Difference between revisions

Let \(A\) be an \(m \times n\) (0,1) matrix, and let \(\sigma_k(A), 0 \leq k \leq m,\) denote the sum of the permanents of all \(k\)-square submatrices of \(A.\) The \textit{rook vector} of \(A\) is defined by \((\sigma_0(A), \sigma_1(A), \dots, \sigma_m(A))^T;\) its components serve as coefficients of the \textit{rook polynomial} \(r_A(x) = \sigma_0(A) + \sigma_1(A) x + \dots + \sigma_m(A) x^m.\) This paper discusses (i) how the permanent of a matrix is related to the rook vectors of certain submatrices of it, and (ii) how to find the rook polynomial of a matrix in terms of the permanents of some other associated matrices. The results are used to evaluate the permanent of certain types of \(n\)-square (0,1) Toeplitz matrices with band width \(\geq n-1.\)