DMTCS Proceedings, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)

Font Size:  Small  Medium  Large

Matrices with restricted entries and q-analogues of permutations (extended abstract)

Joel Brewster Lewis, Ricky Ini Liu, Alejandro H. Morales, Greta Panova, Steven V Sam, Yan Zhang

Abstract


We study the functions that count matrices of given rank over a finite field with specified positions equal to zero. We show that these matrices are q-analogues of permutations with certain restricted values. We obtain a simple closed formula for the number of invertible matrices with zero diagonal, a q-analogue of derangements, and a curious relationship between invertible skew-symmetric matrices and invertible symmetric matrices with zero diagonal. In addition, we provide recursions to enumerate matrices and symmetric matrices with zero diagonal by rank. Finally, we provide a brief exposition of polynomiality results for enumeration questions related to those mentioned, and give several open questions.
Résumé. Nous étudions certaines fonctions qui comptent des matrices à coefficients dans un corps fini d'un rang donné ayant certaines entrées égales à zéro. Nous montrons que ces matrices sont des q-analogues des permutations avec certaines valeurs restreintes, et nous obtenons une formule simple et fermée pour calculer le nombre de matrices inversibles avec zéro sur toute la diagonale. De plus nous donnons des récursions pour énumérer par le rang les matrices et les matrices symétriques avec des zéros sur la diagonale. Pour finir, nous faisons un exposé concis des résultats sur la polynomialité des fonctions énumératives liées à celles qui sont mentionnées antérieurement, et nous incluons plusieurs questions ouvertes.
Resumen. Estudiamos ciertas funciones que cuentan matrices con un rango dado sobre un campo finito y con ciertas entradas iguales a cero. Mostramos que estas matrices son un q-análogo de permutaciones con ciertos valores restringidos. También obtenemos una recursión simple y cerrada para el número de matrices invertibles con ceros en toda la diagonal. Además, damos recursiones para enumerar matrices y matrices simétricas con ceros en la diagonal por rango. Finálmente, damos una exposición breve de resultados sobre la polinomialidad de funciones enumerativas relacionadas a las anteriormente mencionadas e incluimos varias preguntas abiertas.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional