Generalized permutation matrix: Difference between revisions

Revision as of 15:22, 24 March 2005

Latest revision as of 21:04, 14 April 2025

(54 intermediate revisions by 39 users not shown)

Line 1:

{{Short description|Matrix with one nonzero entry in each row and column}}

In [[matrix theorymathematics]], a '''generalized permutation matrix''' (or '''monomial matrix''') is a [[matrix (mathematics)|matrix]] with the same nonzero pattern as a [[permutation matrix]], i.e. there is exactly one nonzero entry in each row and each column. AUnlike morea formalpermutation waymatrix, towhere expressthe thisnonzero propertyentry ismust asbe follows:1, a [[nonsingular]] matrix A isin a generalized permutation matrix iffthe Anonzero entry can be writtenany asnonzero value. An example of a productgeneralized permutation matrix is

:<math> A=DP </math>

where ''D'' is a nonsingular diagonal matrix and ''P'' is a permutation matrix. The set of n &times n generalized permutation matrices with entries in a [[field]] ''F'' forms a [[subgroup]] of the [[general linear group]] ''GL(n,F)'' in which the group of diagonal matrices is a [[normal subgroup]].

:<math>\begin{bmatrix}

An example of a generalized permutation matrix is

:<math>\begin{bmatrix}0 & 0 & 3 & 0\\ 0 & -2 & 0 & 0\\

10 & 0-7 & 0 & 0\\
1 & 0 & 0 & 0\\
0 & 1 0 & 0 & \sqrt2\end{bmatrix}.</math>

== Structure ==

An interesting theorem states the following:

An [[invertible matrix]] ''A'' is a generalized permutation matrix [[if and only if]] it can be written as a product of an invertible [[diagonal matrix]] ''D'' and an (implicitly [[invertible matrix|invertible]]) [[permutation matrix]] ''P'': i.e.,

: If a nonsingular matrix and its inverse are both nonnegative matrices (i.e. matrices with nonnegative entries), then the matrix is a generalized permutation matrix.

:<math> A =DP DP.</math>

===Group structure===

The [[set (mathematics)|set]] of ''n''&thinsp;×&thinsp;''n'' generalized permutation matrices with entries in a [[field (mathematics)|field]] ''F'' forms a [[subgroup]] of the [[general linear group]] GL(''n'', ''F''), in which the group of [[invertible matrix|nonsingular]] diagonal matrices Δ(''n'', ''F'') forms a [[normal subgroup]]. Indeed, over all fields except [[GF(2)]], the generalized permutation matrices are the [[normalizer]] of the diagonal matrices, meaning that the generalized permutation matrices are the ''largest'' subgroup of GL(''n'', ''F'') in which diagonal matrices are normal.

The abstract group of generalized permutation matrices is the [[wreath product]] of ''F''^× and ''S''_''n''. Concretely, this means that it is the [[semidirect product]] of Δ(''n'', ''F'') by the [[symmetric group]] ''S''_''n'':

:''S''_''n'' ⋉ &Delta;(''n'', ''F''),

where ''S''_''n'' acts by permuting coordinates and the diagonal matrices Δ(''n'', ''F'') are [[group isomorphism|isomorphic]] to the ''n''-fold product (''F''^×)^''n''.

To be precise, the generalized permutation matrices are a (faithful) [[linear representation]] of this abstract wreath product: a realization of the abstract group as a subgroup of matrices.

===Subgroups===

* The subgroup where all entries are 1 is exactly the [[permutation matrices]], which is isomorphic to the symmetric group.

* The subgroup where all entries are ±1 is the [[signed permutation matrices]], which is the [[hyperoctahedral group]].

* The subgroup where the entries are ''m''th [[roots of unity]] <math>\mu_m</math> is isomorphic to a [[generalized symmetric group]].

* The subgroup of diagonal matrices is [[abelian group|abelian]], normal, and a maximal abelian subgroup. The [[quotient group]] is the symmetric group, and this construction is in fact the [[Weyl group]] of the general linear group: the diagonal matrices are a [[maximal torus]] in the general linear group (and are their own [[centralizer]]), the generalized permutation matrices are the normalizer of this torus, and the quotient, <math>N(T)/Z(T) = N(T)/T \cong S_n</math> is the Weyl group.

== Properties ==

:* If a nonsingular matrix and its inverse are both [[nonnegative matrices]] (i.e. matrices with nonnegative entries), then the matrix is a generalized permutation matrix.

* The determinant of a generalized permutation matrix is given by <math display="block">\det(G)=\det(P)\cdot \det(D)=\operatorname{sgn}(\pi)\cdot d_{11}\cdot \ldots \cdot d_{nn},</math> where <math>\operatorname{sgn}(\pi)</math> is the [[sign of a permutation|sign]] of the [[permutation]] <math>\pi</math> associated with <math>P</math> and <math>d_{11},\ldots ,d_{nn}</math> are the diagonal elements of <math>D</math>.

== Generalizations ==

One can generalize further by allowing the entries to lie in a [[ring (mathematics)|ring]], rather than in a field. In that case if the non-zero entries are required to be [[unit (ring theory)|units]] in the ring, one again obtains a group. On the other hand, if the non-zero entries are only required to be non-zero, but not necessarily invertible, this set of matrices forms a [[semigroup]] instead.

One may also schematically allow the non-zero entries to lie in a group ''G,'' with the understanding that matrix multiplication will only involve multiplying a single pair of group elements, not "adding" group elements. This is an [[abuse of notation]], since element of matrices being multiplied must allow multiplication and addition, but is suggestive notion for the (formally correct) abstract group <math>G \wr S_n</math> (the wreath product of the group ''G'' by the symmetric group).

==Signed permutation group==

{{further|Hyperoctahedral group}}

A '''signed permutation matrix''' is a generalized permutation matrix whose nonzero entries are ±1, and are the [[integer]] generalized permutation matrices with integer inverse.

===Properties===

* It is the [[Coxeter group]] <math>B_n</math>, and has [[order (group theory)|order]] <math>2^n n!</math>.

* It is the symmetry group of the [[hypercube]] and (dually) of the [[cross-polytope]].

* Its [[index of a subgroup|index]] 2 subgroup of matrices with determinant equal to their underlying (unsigned) permutation is the Coxeter group <math>D_n</math> and is the symmetry group of the [[demihypercube]].

* It is a subgroup of the [[orthogonal group]].

==Applications==

===Monomial representations===

Generalized permutation matrices occur in [[representation theory]] in the context of [[monomial representations]]. A monomial representation of a group ''G'' is a linear representation <math>\, \rho: G \rightarrow GL(n,F) </math> of G (here ''F'' is the defining field of the representation) such that the image <math> \rho(G) </math> is a subgroup of the group of generalized permutation matrices.

{{main|Monomial representation}}

Generalized permutationMonomial matrices occur in [[representation theory]] in the context of [[monomial representationsrepresentation]]s. A monomial representation of a group ''G'' is a linear representation <math>\,{{nowrap|''ρ'' \rho: ''G'' \rightarrow→ GL(''n'', ''F'') </math>}} of ''G'' (here ''F'' is the defining field of the representation) such that the [[image <math>(mathematics)|image]] \rho''ρ''(''G'') </math> is a subgroup of the group of generalized permutationmonomial matrices.

==References==

* {{cite book | last=Joyner | first=David | title=Adventures in group theory. Rubik's cube, Merlin's machine, and other mathematical toys | edition=2nd updated and revised | ___location=Baltimore, MD | publisher=Johns Hopkins University Press | year=2008 | isbn=978-0-8018-9012-3 | zbl=1221.00013 }}

{{Matrix classes}}

[[Category:Matrices (mathematics)]]

[[Category:Permutations]]

[[Category:Sparse matrices]]