Hubbry Logo
Generalized permutation matrixGeneralized permutation matrixMain
Open search
Generalized permutation matrix
Community hub
Generalized permutation matrix
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Generalized permutation matrix
Generalized permutation matrix
Generalized permutation matrix
View on Wikipedia
from Wikipedia

In mathematics, a generalized permutation matrix (or monomial matrix) is a 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

Structure

[edit]

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) permutation matrix P: i.e.,

Group structure

[edit]

The set of n × 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 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 Sn. Concretely, this means that it is the semidirect product of Δ(n, F) by the symmetric group Sn:

Sn ⋉ Δ(n, F),

where Sn acts by permuting coordinates and the diagonal matrices Δ(n, F) are 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

[edit]
  • 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 mth roots of unity is isomorphic to a generalized symmetric group.
  • The subgroup of diagonal matrices is 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, is the Weyl group.

Properties

[edit]
  • 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 where is the sign of the permutation associated with and are the diagonal elements of .

Generalizations

[edit]

One can generalize further by allowing the entries to lie in a ring, rather than in a field. In that case if the non-zero entries are required to be 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 (the wreath product of the group G by the symmetric group).

Signed permutation group

[edit]
Further information: 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

[edit]
  • It is the Coxeter group , and has order .
  • It is the symmetry group of the hypercube and (dually) of the cross-polytope.
  • Its index 2 subgroup of matrices with determinant equal to their underlying (unsigned) permutation is the Coxeter group and is the symmetry group of the demihypercube.
  • It is a subgroup of the orthogonal group.

Applications

[edit]

Monomial representations

[edit]
Main article: Monomial representation

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.

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Generalized permutation matrix

View on Grokipedia
from Grokipedia
A generalized permutation matrix, also known as a monomial matrix, is a square matrix over a field such as or complex numbers that contains exactly one nonzero entry in each row and each column. These nonzero entries can be any elements from the field, distinguishing them from standard matrices, which have entries of 1 or 0. Equivalently, a monomial matrix can be expressed as the product of an invertible and a . The collection of all n×nn \times n monomial matrices over a field FF (such as R\mathbb{R} or C\mathbb{C}) forms a group under matrix multiplication, denoted GPn(F)GP_n(F), which is a subgroup of the general linear group GLn(F)GL_n(F). This group structure arises because the product and inverse of two monomial matrices are also monomial, with the identity matrix serving as the group identity. Monomial matrices are always invertible, and their inverses preserve the monomial form. The determinant of a monomial matrix equals the product of its nonzero entries multiplied by the sign of the associated permutation. Key spectral properties of matrices are tied to the cycle decomposition of the underlying : the eigenvalues are the roots of polynomials derived from the cycles, where for a cycle of length kk with nonzero entries a1,…,aka_1, \dots, a_k, the corresponding factor is tk−a1⋯akt^k - a_1 \cdots a_k. Eigenvectors can be explicitly constructed for each eigenvalue based on the cycle . In applications, monomial matrices appear in , where they model representations of groups, and in computational algebra systems like GAP for constructing transitive group representations. A notable algebraic property is that an invertible has a nonnegative inverse it is .

Definition

Formal definition

A generalized permutation matrix is an n×nn \times n matrix over a field F\mathbb{F} (such as or complex numbers) that has exactly one nonzero entry in each row and each column, with the nonzero entries being arbitrary scalars from F\mathbb{F}. Formally, such a matrix A=(aij)A = (a_{ij}) satisfies aij≠0a_{ij} \neq 0 if and only if j=σ(i)j = \sigma(i) for some σ\sigma of {1,…,n}\{1, \dots, n\}, ensuring precisely one nonzero per row and column. Any generalized permutation matrix can be expressed as A=DPσA = D P_\sigma, where DD is a with nonzero diagonal entries from F\mathbb{F} and PσP_\sigma is the corresponding . This structure is also termed a , reflecting the fact that each row (or column) corresponds to a monomial in the matrix representation of linear transformations. Permutation matrices form the special case where all nonzero entries are 1.

Relation to permutation and diagonal matrices

A generalized permutation matrix, also known as a monomial matrix, admits a canonical decomposition as the product of a and a with nonzero entries on the diagonal. Specifically, for an n×nn \times n generalized permutation matrix AA, there exists a σ∈Sn\sigma \in S_n and nonzero scalars d1,…,dnd_1, \dots, d_n such that A=PσDA = P_\sigma D, where PσP_\sigma is the permutation matrix associated with σ\sigma and D=diag⁡(d1,…,dn)D = \operatorname{diag}(d_1, \dots, d_n). This decomposition is unique up to the choice of ordering the diagonal entries according to the permutation's action, as the positions of the nonzero entries in AA uniquely determine σ\sigma, and the values of those nonzeros determine the did_i. Alternatively, AA can be factored as A=D′PσA = D' P_\sigma for some diagonal D′D' with nonzero entries, though the two forms are related by commutation conditions when the permutation aligns with the diagonal structure. For instance, consider the 2×22 \times 2 matrix (0ab0),\begin{pmatrix} 0 & a \\ b & 0 \end{pmatrix}, where a,b≠0a, b \neq 0. This is a generalized permutation matrix corresponding to the transposition σ=(1 2)\sigma = (1\ 2), and it decomposes as (0ab0)=(0110)(b00a).\begin{pmatrix} 0 & a \\ b & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b & 0 \\ 0 & a \end{pmatrix}. This decomposition establishes a between the set of n×nn \times n generalized permutation matrices over a field (or ring with units) and the set of pairs (σ,(d1,…,dn))(\sigma, (d_1, \dots, d_n)), where σ\sigma is a in the SnS_n and each did_i is a nonzero scalar. The σ\sigma encodes the support (nonzero pattern) of the matrix, while the tuple (d1,…,dn)(d_1, \dots, d_n) captures the magnitudes of the nonzero entries. The term "monomial matrix" originates from the analogy to monomials in the ring of matrices, where each such matrix effectively scales and permutes basis elements in a manner reminiscent of multiplying by a single term in a .

Algebraic Structure

Group under matrix multiplication

The set of all generalized permutation matrices of size n×nn \times n over a field FF, denoted Mn(F)M_n(F), forms a group under , commonly called the monomial group. This group is a of the general linear group GLn(F)\mathrm{GL}_n(F), hence closed under multiplication and inversion, with the product and inverse of any two elements again being generalized permutation matrices. The identity element of Mn(F)M_n(F) is the n×nn \times n , which corresponds to the identity permutation in SnS_n together with all nonzero entries equal to 1. When FF is finite, the order of Mn(F)M_n(F) is n!⋅∣F×∣nn! \cdot |F^\times|^n, where F×F^\times denotes the of nonzero elements of FF; this follows from the n!n! choices for the positions of the nonzero entries (corresponding to permutations in SnS_n) and ∣F×∣|F^\times| choices for each of the nn nonzero entries. The group Mn(F)M_n(F) is isomorphic to the Sn⋉(F×)nS_n \ltimes (F^\times)^n, or equivalently the F×≀SnF^\times \wr S_n, in which SnS_n acts on (F×)n(F^\times)^n by permuting the coordinates: for σ∈Sn\sigma \in S_n and (a1,…,an)∈(F×)n(a_1, \dots, a_n) \in (F^\times)^n, the action is σ⋅(a1,…,an)=(aσ−1(1),…,aσ−1(n))\sigma \cdot (a_1, \dots, a_n) = (a_{\sigma^{-1}(1)}, \dots, a_{\sigma^{-1}(n)}). Under this identification, elements of Mn(F)M_n(F) correspond to pairs (σ,d)(\sigma, d) with σ∈Sn\sigma \in S_n and d=(d1,…,dn)∈(F×)nd = (d_1, \dots, d_n) \in (F^\times)^n, where the associated matrix has nonzero entry did_i in row ii and column σ(i)\sigma(i). The group operation is then given by (σ,d)⋅(τ,e)=(στ,(dieσ−1(i))i=1n)(\sigma, d) \cdot (\tau, e) = (\sigma \tau, (d_i e_{\sigma^{-1}(i)})_{i=1}^n), reflecting the structure.

Subgroups and normal subgroups

The monomial group MnM_n, consisting of all n×nn \times n generalized permutation matrices over a field FF, admits the subgroup of permutation matrices, which is isomorphic to the SnS_n. The subgroup of diagonal matrices with nonzero entries on the diagonal is isomorphic to (F∗)n(F^*)^n, where F∗F^* is the of the field, and this is normal in MnM_n. The full group MnM_n is a (F∗)n⋊Sn(F^*)^n \rtimes S_n, with SnS_n acting by of the coordinates. The center Z(Mn)Z(M_n) of the monomial group is the subgroup of scalar matrices λI\lambda I with λ∈F∗\lambda \in F^*, isomorphic to F∗F^*. The derived subgroup [Mn,Mn][M_n, M_n] is the special monomial group, comprising all monomial matrices with determinant 1. This subgroup plays a key algebraic role as the kernel of the determinant homomorphism det⁡:Mn→F∗\det: M_n \to F^*, which is surjective, making the abelianization of MnM_n isomorphic to F∗F^*. The quotient Mn/Z(Mn)M_n / Z(M_n) has a structure related to the , particularly in cases where the field allows signed entries; for example, over R\mathbb{R} or C\mathbb{C}, it aligns with the hyperoctahedral group Sn≀Z2S_n \wr \mathbb{Z}_2 when considering signed matrices modulo scalars. Cyclic subgroups of MnM_n are generated by individual elements; for instance, a monomial matrix corresponding to a k-cycle with all nonzero entries equal to some λ∈F∗\lambda \in F^* generates a cyclic of order k. In the context of algebraic groups over fields, the monomial group MnM_n intersects with Borel subgroups of GLn(F)GL_n(F), such as the upper triangular matrices, yielding solvable subgroups like the diagonal torus itself, which is a maximal torus in MnM_n. Parabolic subgroups of GLn(F)GL_n(F), stabilizers of partial flags, intersect MnM_n in subgroups that preserve the flag structure under permutation actions, providing important normal solvable subgroups for decomposition theory.

Key Properties

Invertibility and determinants

Every generalized permutation matrix, also known as a monomial matrix, is invertible, as it can be expressed as the product of an invertible permutation matrix PσP_\sigma and an invertible diagonal matrix DD with nonzero diagonal entries di≠0d_i \neq 0 for all ii, and the product of invertible matrices is invertible. Specifically, if A=PσDA = P_\sigma D, then the inverse is given by A−1=D−1Pσ−1=D−1PσT,A^{-1} = D^{-1} P_\sigma^{-1} = D^{-1} P_\sigma^T, where D−1D^{-1} is the diagonal matrix with entries 1/di1/d_i and PσTP_\sigma^T is the transpose of the permutation matrix, which is itself a permutation matrix corresponding to the inverse permutation σ−1\sigma^{-1}; thus, the inverse is also a generalized permutation matrix. The determinant of a generalized permutation matrix A=PσDA = P_\sigma D is computed as det⁡(A)=det⁡(Pσ)det⁡(D)=sgn⁡(σ)∏i=1ndi,\det(A) = \det(P_\sigma) \det(D) = \operatorname{sgn}(\sigma) \prod_{i=1}^n d_i, where sgn⁡(σ)\operatorname{sgn}(\sigma) is the of the σ\sigma (equal to +1+1 for even permutations and −1-1 for odd permutations) and ∏i=1ndi\prod_{i=1}^n d_i is the product of the nonzero entries did_i. This formula follows from the multiplicativity of the and the known of permutation matrices. The set of all n×nn \times n generalized permutation matrices over a field FF (with nonzero entries from FF) forms a of the GLn(F)\mathrm{GL}_n(F) under , known as the monomial group; this is generated by the and the diagonal matrices with units on the diagonal. Closure under multiplication and inversion ensures the group structure, with the serving as the neutral element.

Eigenvalues and traces

The eigenvalues of a generalized permutation matrix A∈Mn(C)A \in M_n(\mathbb{C}) are determined by the cycle decomposition of the underlying σ\sigma. Specifically, if σ\sigma decomposes into disjoint cycles, then for each cycle of length kk with nonzero entries aj1,…,ajka_{j_1}, \dots, a_{j_k} along the cycle positions, the corresponding eigenvalues are the kk distinct complex numbers λ\lambda satisfying λk=∏m=1kajm\lambda^k = \prod_{m=1}^k a_{j_m}, provided the characteristic does not divide kk. These are given explicitly as λr=(∏m=1kajm)1/kωr\lambda_r = \left( \prod_{m=1}^k a_{j_m} \right)^{1/k} \omega^r, where ω=e2πi/k\omega = e^{2\pi i / k} is a primitive kk-th and r=0,1,…,k−1r = 0, 1, \dots, k-1. For cycles of length 1 (fixed points), the eigenvalue is simply the corresponding nonzero diagonal entry di=aiid_i = a_{ii}. The of AA factors according to the cycle structure: det⁡(λI−A)=∏(λkℓ−cℓ)\det(\lambda I - A) = \prod (\lambda^{k_\ell} - c_\ell), where the product runs over all cycles ℓ\ell, kℓk_\ell is the length of cycle ℓ\ell, and cℓ=∏ajc_\ell = \prod a_{j} is the product of the nonzero entries along that cycle. This polynomial has no zero eigenvalues, as all cℓ≠0c_\ell \neq 0 and are nonzero. Algebraic multiplicities are 1 for each distinct root unless multiple cycles yield the same root values, but in over C\mathbb{C}, all eigenvalues have multiplicity 1 per cycle contribution. The trace of AA, which equals the sum of its eigenvalues, simplifies to the sum of the nonzero diagonal entries: tr⁡(A)=∑i:σ(i)=idi\operatorname{tr}(A) = \sum_{i: \sigma(i)=i} d_i. This follows because the sum of eigenvalues over any cycle of k>1k > 1 is zero (as the sum of the kk-th roots of unity is zero), while for length-1 cycles it is did_i. Over an such as C\mathbb{C}, generalized permutation matrices are always diagonalizable. For each cycle block, the k×kk \times k submatrix has distinct eigenvalues (the kk distinct kk-th roots of cc), so its minimal has distinct roots, ensuring the geometric multiplicity equals the algebraic multiplicity. The full matrix, being block-diagonalizable in a suitable basis aligned with the cycles, inherits this property.

Signed Permutation Matrices

Definition and examples

A signed permutation matrix is a square matrix of size n×nn \times n that contains exactly one nonzero entry in each row and each column, with each nonzero entry being either +1+1 or −1-1. This structure positions signed permutation matrices as a special subset of generalized permutation matrices, where the nonzero entries are restricted to the values ±1\pm 1. Such matrices can be constructed as the product of a standard permutation matrix and a diagonal matrix whose diagonal entries are ±1\pm 1. Algebraically, this corresponds to the action of signed permutations, which form the wreath product Sn⋉(Z/2Z)nS_n \ltimes (\mathbb{Z}/2\mathbb{Z})^n, where SnS_n is the symmetric group on nn elements and Z/2Z\mathbb{Z}/2\mathbb{Z} accounts for the sign flips. For n=2n=2, the signed permutation matrices include the identity matrix (1001),\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, the standard swap (0110),\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, a signed swap (01−10),\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}, and another signed variant (0−110).\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}. These examples illustrate how sign changes introduce reflections while preserving the permutation structure. The full set for n=2n=2 comprises eight matrices, reflecting the group order of 2nn!=82^n n! = 8. The collection of all n×nn \times n signed permutation matrices under forms a group of order 2nn!2^n n!, known as the hyperoctahedral group BnB_n, which coincides with the of types BnB_n or CnC_n in the classification of Coxeter groups. This group structure has been studied since the early development of Coxeter groups in , with signed matrices providing a concrete matrix realization.

Group-theoretic properties

The group of signed permutation matrices forms the hyperoctahedral group BnB_n, which is isomorphic to the Sn⋉(Z/2Z)nS_n \ltimes (\mathbb{Z}/2\mathbb{Z})^n, where SnS_n acts by permuting the coordinates of (Z/2Z)n(\mathbb{Z}/2\mathbb{Z})^n, corresponding to independent sign changes on the vectors. This structure captures the combined action of permuting basis vectors and flipping their signs. The group admits a presentation via generators consisting of adjacent transpositions sis_i (swapping positions ii and i+1i+1, for i=1,…,n−1i = 1, \dots, n-1) and sign flips tit_i (changing the at position ii, for i=1,…,ni = 1, \dots, n). The relations include the Coxeter relations for the sis_i (with si2=1s_i^2 = 1 and braid relations (sisi+1)3=1(s_i s_{i+1})^3 = 1 for adjacent indices), the conditions ti2=1t_i^2 = 1 and titj=tjtit_i t_j = t_j t_i for i≠ji \neq j, and the semidirect product relations sktjsk−1=tsk(j)s_k t_j s_k^{-1} = t_{s_k(j)}. An equivalent Coxeter presentation uses simple reflections s0,s1,…,sn−1s_0, s_1, \dots, s_{n-1}, where s0s_0 flips the of the first position, sis_i (for i≥1i \geq 1) are adjacent transpositions, all satisfying sk2=1s_k^2 = 1, with braid relations (sisi+1)3=1(s_i s_{i+1})^3 = 1 for i≥1i \geq 1, (s0s1)4=1(s_0 s_1)^4 = 1, and commuting relations sisj=sjsis_i s_j = s_j s_i for ∣i−j∣>1|i - j| > 1. For n≥2n \geq 2, the center of BnB_n consists of the II and the central sign flip −I-I (the with all entries -1), which commutes with all elements due to the balanced sign changes across permutations and flips. As the Weyl group of the root systems of types BnB_n and CnC_n, the irreducible representations of BnB_n over C\mathbb{C} are parameterized by pairs of partitions (λ,μ)(\lambda, \mu) with ∣λ∣+∣μ∣=n|\lambda| + |\mu| = n, where the dimension of the representation indexed by (λ,μ)(\lambda, \mu) is given by the product of hook-length formulas for λ\lambda and μ\mu. The length function ℓ(w)\ell(w) with respect to the Coxeter generators counts the minimal number of simple reflections in a reduced expression for w∈Bnw \in B_n, equivalently ℓ(w)=\inv(w)+¬(w)\ell(w) = \inv(w) + \neg(w), where \inv(w)\inv(w) is the number of inversion pairs (i<j)(i < j) with w(i)>w(j)w(i) > w(j) (considering the absolute values and order on signed elements), and ¬(w)\neg(w) is the number of negative entries in the one-line notation of ww. The Bruhat order on BnB_n extends that of SnS_n, defined by u≤wu \leq w if some reduced expression for ww contains a reduced expression for uu as a subword, or equivalently via the tableau criterion adapted to signed entries; this poset is a lattice with Eulerian properties and shellable intervals. Signed permutation matrices form a subgroup of the monomial group.

Generalizations

Over arbitrary fields and rings

The concept of generalized permutation matrices, also known as monomial matrices, extends naturally to arbitrary fields FF. A matrix in Mn(F)M_n(F) is monomial if it has exactly one nonzero entry in each row and each column, with those entries belonging to F∖{0}F \setminus \{0\}. Since fields have no zero divisors, every such matrix is invertible over FF, with the inverse also monomial. The set of all invertible n×nn \times n monomial matrices forms a subgroup of GLn(F)\mathrm{GL}_n(F), isomorphic to the wreath product F×≀SnF^\times \wr S_n, where F×F^\times is the multiplicative group of nonzero elements of FF and SnS_n is the symmetric group on nn letters. This group structure arises from the semidirect product of the normal subgroup of diagonal matrices with nonzero entries (isomorphic to (F×)n(F^\times)^n) by the permutation matrices (isomorphic to SnS_n). Unlike the real or complex case, where ∣F×∣|F^\times| is infinite, over finite fields F=FqF = \mathbb{F}_q, the order of the group is (q−1)nn!(q-1)^n n!. Over commutative rings RR, the definition adapts to require that the nonzero entries lie in the group of units U(R)U(R) to ensure invertibility. A monomial matrix over RR is thus invertible if and only if its nonzero entries are units in RR, forming the subgroup of units in the matrix ring Mn(R)M_n(R) with monomial support. This subgroup is isomorphic to the wreath product U(R)≀SnU(R) \wr S_n. For example, over the integers Z\mathbb{Z}, where U(Z)={±1}U(\mathbb{Z}) = \{\pm 1\}, the invertible monomial matrices reduce precisely to the signed permutation matrices. Similarly, over the polynomial ring kk for a field kk, the units are the nonzero constants k×k^\times, so the monomial matrices in GLn(k)\mathrm{GL}_n(k) have nonzero entries from k×k^\times. Properties of these matrices adjust accordingly for non-field rings. The determinant of an invertible monomial matrix over RR is the product of its nonzero entries multiplied by the sign of the underlying , hence lies in U(R)U(R). Unlike over fields, eigenvalues are not generally defined, as the ring may lack the necessary division properties for solving the characteristic equation. In the tropical semiring (using min-plus algebra), a brief generalization replaces the usual and with tropical operations, yielding "tropical monomial matrices" with exactly one finite entry per row and column, useful in optimization contexts but diverging from classical invertibility.

Infinite-dimensional and operator analogs

In the infinite-dimensional setting, generalized permutation matrices arise as operators on separable Hilbert spaces with countable orthonormal bases, such as ℓ2(N)\ell^2(\mathbb{N}) or ℓ2(Z)\ell^2(\mathbb{Z}). For a countable basis {ei}i∈I\{e_i\}_{i \in I}, where II is countable, a generalized permutation operator TT is defined such that Tei=cieσ(i)T e_i = c_i e_{\sigma(i)} for some σ:I→I\sigma: I \to I and scalars ci≠0c_i \neq 0, generalizing the finite-dimensional case where exactly one nonzero entry appears per row and column. If the cic_i are bounded and the operator is bounded, it represents an infinite matrix with finitely or infinitely many nonzeros per row and column, but precisely one per row and column corresponding to the permutation structure; for bi-infinite indices (I=ZI = \mathbb{Z}), σ\sigma is a bi-infinite ensuring the action preserves the space. On the Hilbert space ℓ2(N)\ell^2(\mathbb{N}), bounded monomial operators include multiplication by a bounded sequence of phases followed by a permutation of the basis vectors, yielding unitary operators when ∣ci∣=1|c_i| = 1 for all ii and σ\sigma is a bijection. The unilateral shift operator SS, defined by Sen=en+1S e_n = e_{n+1} for n≥1n \geq 1, exemplifies a monomial operator that is an isometry but not unitary, as it fails to be surjective on the basis. In contrast, on ℓ2(Z)\ell^2(\mathbb{Z}), the bilateral shift Uen=en+1U e_n = e_{n+1} is a unitary monomial operator corresponding to the infinite cyclic permutation. The group of all such unitary monomial operators forms the infinite monomial group, isomorphic to the wreath product of the circle group T\mathbb{T} (unitary scalars) with the infinite symmetric group S∞S_\infty, where S∞S_\infty acts by permuting the basis via unitary representations Uσf(n)=f(σ−1(n))U_\sigma f(n) = f(\sigma^{-1}(n)). Properties of these operators extend finite-dimensional analogs but account for infinitude: the spectrum of a unitary monomial operator T=DUσT = D U_\sigma, where DD is diagonal unitary, is the closure of the set {ci:i∈I}\{c_i : i \in I\} on the unit circle, reflecting the discrete eigenvalues from the phases. Not all monomial operators are invertible; for instance, weighted shifts with weights approaching zero have zero in the spectrum and are not bounded below, hence noninvertible, unlike their finite-dimensional counterparts which are invertible if nonzero entries are nonzero. The finitary monomial group, a subgroup where permutations move only finitely many basis vectors, serves as the minimal infinite generalization of finite complete monomial groups and embeds densely in the full infinite monomial group via direct limits. The C*-algebra generated by the monomial unitaries coincides with the group C*-algebra of the wreath product T≀S∞\mathbb{T} \wr S_\infty, capturing the operator-theoretic structure through its unitary representations on ℓ2\ell^2.

Applications

Monomial representations in group theory

In group theory, a representation of a GG is a linear representation ρ:G→GL(V)\rho: G \to \mathrm{GL}(V) over C\mathbb{C} such that there exists a basis of VV in which every matrix ρ(g)\rho(g) is , meaning it has exactly one nonzero entry in each row and each column, thus forming a generalized permutation matrix up to scaling of the entries. Equivalently, the image of ρ\rho lies in the group of matrices. This arises naturally from : specifically, if χ\chi is a one-dimensional (linear) representation of a H≤GH \leq G, then the IndHGχ\mathrm{Ind}_H^G \chi admits a basis consisting of representatives, in which the action of GG permutes the basis vectors up to multiplication by the values of χ\chi, yielding matrices. Every irreducible representation is thus induced from a linear character of some , though not all representations need be induced in this way. In , the characters of representations, known as monomial characters, are precisely those induced from linear characters of subgroups. For a linear character χ\chi of H≤GH \leq G, the induced character χG\chi^G is given by χG(g)=1∣H∣∑x∈Gχ^(x−1gx),\chi^G(g) = \frac{1}{|H|} \sum_{x \in G} \hat{\chi}(x^{-1} g x), where χ^\hat{\chi} extends χ\chi by zero outside HH. This formula reflects summation over the double cosets or, in the case of the , simplifies to χG(1)=∣G:H∣\chi^G(1) = |G:H|, highlighting the dimension scaling by the index. Groups in which all irreducible characters are monomial are termed MM-groups, including all pp-groups and supersolvable groups. Clifford theory further elucidates the role of representations in relating representations of a group to those of its subgroups. For a N⊴GN \trianglelefteq G and an ρ\rho of GG, the restriction ρ∣N\rho|_N decomposes into a of irreducible representations of NN that are conjugate under GG; if ρ\rho is monomial, this decomposition stabilizes under GG-conjugation, preserving the structure in suitable bases. This stability implies that representations of GG induce actions on the isotypic components over NN. A concrete example occurs with the SnS_n: its decomposes as a of all irreducible representations, each of which appears as a constituent in some monomial representation of SnS_n. This realization underscores how generalized permutation matrices capture the permutation aspects underlying the Specht module irreducibles. For groups where not all irreducibles are monomial, quasimonomial representations provide a generalization for "near-monomial" cases, where characters are induced from representations that are linear on subgroups but more broadly. Such structures extend the theory to supercharacter frameworks, allowing analysis of groups with partial behavior.

Uses in quantum computing and physics

In quantum computing, generalized permutation matrices, also known as monomial unitaries, serve as a foundational representation for the Clifford group, the normalizer of the Weyl-Heisenberg group generated by Pauli operators. These matrices combine permutations of basis states with phase factors, effectively generalizing the action of Pauli operators by allowing controlled swaps and relative phases, which is crucial for constructing fault-tolerant circuits. For instance, when the Hilbert space dimension is a perfect square, every Clifford operator can be expressed as a monomial phase-permutation matrix, enabling efficient simulation and decomposition of quantum gates. This representation extends the Clifford group by incorporating higher-level operations in the Clifford hierarchy, where monomial forms facilitate the implementation of non-Clifford gates through compilation into permutation-based circuits. In physics, signed generalized permutation matrices model symmetry operations in crystal lattices, particularly for point groups that include reflections and inversions, where the nonzero entries are ±1 to account for orientation-reversing transformations. These matrices represent the rotational and reflectional symmetries of the lattice, preserving the crystal's periodic structure under group actions, as seen in the Seitz notation for space groups where the linear part is a signed permutation. In tight-binding models for electronic structure, generalized permutation matrices enable changes of basis by relabeling atomic sites and applying site-dependent phases, simplifying the Hamiltonian diagonalization while maintaining sparsity in the hopping matrix. Generalized permutation matrices find application in through their role in multirate systems, where the permutation component handles reordering of signal coefficients and the diagonal scaling adjusts amplitudes in filter banks. In wavelet transforms, matrices facilitate efficient implementations of orthogonal block transforms by combining decimation (via ) with normalization (via scaling), reducing computational complexity in schemes. This structure exploits the sparsity of monomial forms to optimize pyramid algorithms for and analysis. In numerical methods, the structure of generalized permutation matrices supports techniques, as their single nonzero entry per row and column allows for rapid pivoting and reordering in direct solvers like LU factorization. When solving linear systems with monomial sparsity patterns, such as in structured grid problems, permutation-based preconditioners exploit this form to minimize fill-in during elimination, enhancing for large-scale computations without dense approximations. A key example arises in , where matrices model transversal gates in stabilizer codes, acting independently on each to implement logical operations while preserving the code subspace. For instance, in cluster-state-based codes derived from finite groups, stabilizers are matrices that detect phase and bit-flip errors without propagating them across qubits, enabling robust encoding for measurement-based . Additionally, generalized permutation matrices play a role in adiabatic for sorting algorithms, where matrices encode the target ordering in problems mapped to stoquastic Hamiltonians. By evolving from an initial Hamiltonian to one penalizing invalid permutations, adiabatic passage yields the sorted configuration as the , with scaling factors in forms adjusting for weighted sorting criteria.

References

  1. https://core.ac.uk/download/pdf/41824776.pdf
  2. https://arxiv.org/pdf/1803.02199
  3. https://digitalresearch.bsu.edu/mathexchange/wp-content/uploads/2023/12/2023_3_MP.pdf
  4. https://repository.arizona.edu/bitstream/handle/10150/244772/azu_etd_mr_2012_0149_sip1_m.pdf?sequence=1
  5. https://arxiv.org/pdf/2510.22877
  6. https://arxiv.org/pdf/2212.13291
  7. https://link.springer.com/article/10.1007/s10468-016-9633-4
  8. https://arxiv.org/abs/1804.04702
  9. https://books.google.com/books/about/Linear_Algebraic_Groups.html?id=7hTTBwAAQBAJ
  10. https://mathoverflow.net/questions/127447/wreath-product-and-matrix-presentation
  11. https://www.math.uwaterloo.ca/~cgodsil/quagmire/pdfs/LA.pdf
  12. https://people.brandeis.edu/~igusa/Math101bS07/Math101b_notesD.pdf
  13. https://arxiv.org/pdf/1608.07864
  14. https://mathoverflow.net/questions/81805/restriction-of-characters-of-hyperoctahedral-groups
  15. https://math.soimeme.org/~arunram/Notes/hyperoctahedral.html
  16. https://yorkspace.library.yorku.ca/server/api/core/bitstreams/aa18a431-3383-4e17-9ada-d32d82a8381e/content
  17. https://alco.centre-mersenne.org/item/10.5802/alco.316.pdf
  18. https://arxiv.org/pdf/1912.08576
  19. https://sites.math.washington.edu/~billey/classes/reflection.groups/references/EntireBook.pdf
  20. https://pubs.aip.org/aip/jmp/article-pdf/30/11/2469/19310047/2469_1_online.pdf
  21. https://arxiv.org/pdf/2504.09560
  22. https://www.combinatorics.org/ojs/index.php/eljc/article/download/v20i4p36/pdf/
  23. https://www.mat.univie.ac.at/~slc/wpapers/s34bayreuth.pdf
  24. https://link.springer.com/article/10.1007/s11253-017-1413-8
  25. https://dspace.mit.edu/bitstream/handle/1721.1/107447/10468_2016_9633_ReferencePDF.pdf?sequence=1&isAllowed=y
  26. https://onlinelibrary.wiley.com/doi/10.1155/2018/4797638
  27. https://mat.polsl.pl/groups/docs/sushchanskyy.pdf
  28. http://iitp.ru/upload/userpage/52/Book2016Feb26.pdf
  29. https://johnmccarthymath.com/wp-content/uploads/2022/07/BoundedMonomialOperators.pdf
  30. https://mathoverflow.net/questions/347897/the-notions-of-monomial-and-induced-monomial-in-representation-theory
  31. https://projecteuclid.org/journals/nagoya-mathematical-journal/volume-35/issue-none/Monomial-representations-and-metabelian-groups/nmj/1118797732.pdf
  32. https://duncan.math.sc.edu/s23/math742/notes/induction.pdf
  33. https://scholarworks.uvm.edu/cgi/viewcontent.cgi?article=1571&context=graddis
  34. http://sporadic.stanford.edu/Math122/lecture12.pdf
  35. https://www-users.cse.umn.edu/~webb/RepBook/RepBookLatex.pdf
  36. https://www.cambridge.org/core/books/representation-theory-of-the-symmetric-group/ordinary-irreducible-representations-and-characters-of-symmetric-and-alternating-groups/81FDA40F116610208CD5E0002D4CA6BE
  37. https://dml.cz/bitstream/handle/10338.dmlcz/151130/CzechMathJ_72-2022-4_12.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.