Generalized permutation matrix: Difference between revisions

Revision as of 00:03, 25 March 2005

Latest revision as of 21:04, 14 April 2025

(53 intermediate revisions by 38 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 ''A''nonzero entry can be writtenany asnonzero value. An example of a productgeneralized permutation matrix is

:<math> A=DP </math>\begin{bmatrix}

0 & 0 & 3 & 0\\

0 & -7 & 0 & 0\\

1 & 0 & 0 & 0\\

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

== Structure ==

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]].

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.,

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

An example of a generalized permutation matrix is

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

1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}</math>

===Group structure===

An interesting theorem states the following:

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.

: 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 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]]