Content deleted Content added
m Moving Category:Matrices to Category:Matrices (mathematics) per Wikipedia:Categories for discussion/Speedy |
|||
| (42 intermediate revisions by 31 users not shown) | |||
Line 1:
{{Short description|Matrix with one nonzero entry in each row and column}}
In [[mathematics]], 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. Unlike a permutation matrix, where the nonzero entry must be 1, in a generalized permutation matrix the nonzero entry can be any nonzero value. An example of a generalized permutation matrix is
:<math>\begin{bmatrix}
0 & 0 & 3 & 0\\
0 & -
1 & 0 & 0 & 0\\
0 & 0 & 0 &
== Structure ==
:<math>
===Group structure===
An interesting theorem states the following: 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 [[set (mathematics)|set]] of ''n''&
The abstract group of generalized permutation matrices is the [[wreath product]] of ''F''<sup>×</sup> and ''S''<sub>''n''</sub>. Concretely, this means that it is the [[semidirect product]] of Δ(''n'', ''F'') by the [[symmetric group]] ''S''<sub>''n''</sub>:
:''S''<sub>''n''</sub> ⋉ Δ(''n'', ''F''),
where ''S''<sub>''n''</sub> acts by permuting coordinates and the diagonal matrices Δ(''n'', ''F'') are [[group isomorphism|isomorphic]] to the ''n''-fold product (''F''<sup>×</sup>)<sup>''n''</sup>.
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 ==
▲
* 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
===Properties===
* It is the [[Coxeter group]] <math>B_n</math>, and has [[order (group theory)|order]] <math>2^
* 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]].
==
===Monomial representations===
▲The set of ''n''×''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 nonsingular diagonal matrices Δ(''n'', ''F'') forms a [[normal subgroup]]. One can show that the group of ''n''×''n'' generalized permutation matrices is a [[semidirect product]] of Δ(''n'', ''F'') by the [[symmetric group]] ''S''<sub>''n''</sub>:
{{main|Monomial representation}}
Monomial matrices occur in [[representation theory]] in the context of [[monomial
==
* {{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}}
▲Monomial matrices occur in [[representation theory]] in the context of [[monomial representations]]. A monomial representation of a group ''G'' is a linear representation ''ρ'' : ''G'' → GL(''n'', ''F'' ) of ''G'' (here ''F'' is the defining field of the representation) such that the image ''ρ''(''G'' ) is a subgroup of the group of monomial matrices.
[[Category:Matrices (mathematics)]]
[[Category:Permutations]]
[[Category:Sparse matrices]]
| |||