Quelle chap5_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/repndecomp/doc/chap5_mj.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (RepnDecomp) - Chapter 5: Computing decompositions of representations</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap5" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>

<a href="chap5.html">[MathJax off]</a>
<a id="X7F968DF987DE4A6E" name="X7F968DF987DE4A6E"></a>
<div class="ChapSects"><a href="chap5_mj.html#X7F968DF987DE4A6E">5 Computing decompositions of representations</a>
<div class="ContSect"> <a href="chap5_mj.html#X7E29883984400D2C">5.1 Block diagonalizing</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X8361AD057AD282AC">5.1-1 BlockDiagonalBasisOfRepresentation</a>
 <a href="chap5_mj.html#X86EB837579C1416D">5.1-2 BlockDiagonalRepresentation</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X863A16A179A7486B">5.2 Algorithms due to the authors</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X831574AD864C94A8">5.2-1 REPN_ComputeUsingMyMethod</a>
 <a href="chap5_mj.html#X7DB659DB7E48D502">5.2-2 REPN_ComputeUsingMyMethodCanonical</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7C22F13E80A74438">5.3 Algorithms due to Serre</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7E95B0367992BEC4">5.3-1 CanonicalDecomposition</a>
 <a href="chap5_mj.html#X795C63F386C45308">5.3-2 IrreducibleDecomposition</a>
 <a href="chap5_mj.html#X87E91CBE7992D126">5.3-3 IrreducibleDecompositionCollected</a>
 <a href="chap5_mj.html#X7C1CF0547D72D354">5.3-4 REPN_ComputeUsingSerre</a>
</div></div>
</div>

<h3>5 Computing decompositions of representations</h3>

<a id="X7E29883984400D2C" name="X7E29883984400D2C"></a>

<h4>5.1 Block diagonalizing</h4>

Given a representation \(\rho : G \to GL(V)\), it is often desirable to find a basis for \(V\) that block diagonalizes each \(\rho(g)\) with the block sizes being as small as possible. This speeds up matrix algebra operations, since they can now be done block-wise.

<a id="X8361AD057AD282AC" name="X8361AD057AD282AC"></a>

<h5>5.1-1 BlockDiagonalBasisOfRepresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlockDiagonalBasisOfRepresentation</code>( <var class="Arg">rho</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: Basis for \(V\) that block diagonalizes \(\rho\).

Let \(G\) have irreducible representations \(\rho_i\), with dimension \(d_i\) and multiplicity \(m_i\). The basis returned by this operation gives each \(\rho(g)\) as a block diagonal matrix which has \(m_i\) blocks of size \(d_i \times d_i\) for each \(i\).

<a id="X86EB837579C1416D" name="X86EB837579C1416D"></a>

<h5>5.1-2 BlockDiagonalRepresentation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlockDiagonalRepresentation</code>( <var class="Arg">rho</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: Representation of \(G\) isomorphic to \(\rho\) where the images \(\rho(g)\) are block diagonalized.

This is just a convenience operation that uses <code class="func">BlockDiagonalBasisOfRepresentation</code> (<a href="chap5_mj.html#X8361AD057AD282AC">5.1-1</a>) to calculate the basis change matrix and applies it to put \(\rho\) into the block diagonalised form.

<a id="X863A16A179A7486B" name="X863A16A179A7486B"></a>

<h4>5.2 Algorithms due to the authors</h4>

<a id="X831574AD864C94A8" name="X831574AD864C94A8"></a>

<h5>5.2-1 REPN_ComputeUsingMyMethod</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ REPN_ComputeUsingMyMethod</code>( <var class="Arg">rho</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A record in the same format as <code class="func">REPN_ComputeUsingSerre</code> (<a href="chap5_mj.html#X7C1CF0547D72D354">5.3-4</a>)

Computes the same values as <code class="func">REPN_ComputeUsingSerre</code> (<a href="chap5_mj.html#X7C1CF0547D72D354">5.3-4</a>), taking the same options. The heavy lifting of this method is done by <code class="func">LinearRepresentationIsomorphism</code> (<a href="chap2_mj.html#X7F0D3CFB7800149A">2.1-1</a>), where there are some further options that can be passed to influence algorithms used.

<div class="example"><pre>
gap> G := SymmetricGroup(4);;
gap> irreps := IrreducibleRepresentations(G);;
gap> rho := DirectSumOfRepresentations([irreps[4], irreps[5]]);;
gap> # Jumble rho up a bit so it's not so easy for the library.
> A := [ [ 3, -3, 2, -4, 0, 0 ], [ 4, 0, 1, -5, 1, 0 ], [ -3, -1, -2, 4, -1, -2 ],
> [ 4, -4, -1, 5, -3, -1 ], [ 3, -2, 1, 0, 0, 0 ], [ 4, 2, 4, -1, -2, 1 ] ];;
gap> rho := ComposeHomFunction(rho, B -> A^-1 * B * A);;
gap> # We've constructed rho from two degree 3 irreps, so there are a few
> # things we can check for correctness:
> decomposition := REPN_ComputeUsingMyMethod(rho);;
gap> # Two distinct irreps, so the centralizer has dimension 2
> Length(decomposition.centralizer_basis) = 2;
true
gap> # Two distinct irreps i.e. two invariant subspaces
> Length(decomposition.decomposition) = 2;
true
gap> # All subspaces are dimension 3
> ForAll(decomposition.decomposition, Vs -> Length(Vs) = 1 and Dimension(Vs[1]) = 3);
true
gap> # And finally, check that the block diagonalized representation
> # computed is actually isomorphic to rho:
> AreRepsIsomorphic(rho, decomposition.diagonal_rep);
true
</pre></div>

<a id="X7DB659DB7E48D502" name="X7DB659DB7E48D502"></a>

<h5>5.2-2 REPN_ComputeUsingMyMethodCanonical</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ REPN_ComputeUsingMyMethodCanonical</code>( <var class="Arg">rho</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A record in the same format as <code class="func">REPN_ComputeUsingMyMethod</code> (<a href="chap5_mj.html#X831574AD864C94A8">5.2-1</a>).

Performs the same computation as <code class="func">REPN_ComputeUsingMyMethod</code> (<a href="chap5_mj.html#X831574AD864C94A8">5.2-1</a>), but first splits the representation into canonical summands using <code class="func">CanonicalDecomposition</code> (<a href="chap5_mj.html#X7E95B0367992BEC4">5.3-1</a>). This might reduce the size of the matrices we need to work with significantly, so could be much faster.

If the option <code class="code">parallel</code> is given, the decomposition of canonical summands into irreps is done in parallel, which could be much faster.

<div class="example"><pre>
gap> # This is the same example as before, but splits into canonical
> # summands internally. It gives exactly the same results, up to
> # isomorphism.
> other_decomposition := REPN_ComputeUsingMyMethodCanonical(rho);;
gap> Length(other_decomposition.centralizer_basis) = 2;
true
gap> Length(other_decomposition.decomposition) = 2;
true
gap> ForAll(other_decomposition.decomposition, Vs -> Length(Vs) = 1 and Dimension(Vs[1]) = 3);
true
gap> AreRepsIsomorphic(rho, other_decomposition.diagonal_rep);
true
</pre></div>

<a id="X7C22F13E80A74438" name="X7C22F13E80A74438"></a>

<h4>5.3 Algorithms due to Serre</h4>

Note: all computation in this section is actually done in the function <code class="func">REPN_ComputeUsingSerre</code> (<a href="chap5_mj.html#X7C1CF0547D72D354">5.3-4</a>), the other functions are wrappers around it.

<a id="X7E95B0367992BEC4" name="X7E95B0367992BEC4"></a>

<h5>5.3-1 CanonicalDecomposition</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalDecomposition</code>( <var class="Arg">rho</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: List of vector spaces \(V_i\), each \(G\)-invariant and a direct sum of isomorphic irreducibles. That is, for each \(i\), \(V_i \cong \oplus_j W_i\) (as representations) where \(W_i\) is an irreducible \(G\)-invariant vector space.

Computes the canonical decomposition of \(V\) into \(\oplus_i\;V_i\) using the formulas for projections \(V \to V_i\) due to Serre. You can pass in the option <code class="code">irreps</code> with a list of irreps of \(G\), and this will be used instead of computing a complete list ourselves. If you already know which irreps will appear in \(\rho\), for instance, this will save time.

<div class="example"><pre>
gap> # This is the trivial group
> G := Group(());;
gap> # The trivial group has only one representation per degree, so a
> # degree d representation decomposes into a single canonical summand
> # containing the whole space
> rho := FuncToHom@RepnDecomp(G, g -> IdentityMat(3));;
gap> canonical_summands_G := CanonicalDecomposition(rho);
[ ( Cyclotomics^3 ) ]
gap> # More interesting example, S_3
> H := SymmetricGroup(3);;
gap> # The standard representation: a permutation to the corresponding
> # permutation matrix.
> tau := FuncToHom@RepnDecomp(H, h -> PermutationMat(h, 3));;
gap> # Two canonical summands corresponding to the degree 2 and
> # trivial irreps (in that order)
> List(CanonicalDecomposition(tau), Dimension);
[ 2, 1 ]
</pre></div>

<a id="X795C63F386C45308" name="X795C63F386C45308"></a>

<h5>5.3-2 IrreducibleDecomposition</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IrreducibleDecomposition</code>( <var class="Arg">rho</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: List of vector spaces \(W_j\) such that \(V = \oplus_j W_j\) and each \(W_j\) is an irreducible \(G\)-invariant vector space.

Computes the decomposition of \(V\) into irreducible subprepresentations.

<div class="example"><pre>
gap> # The trivial group has 1 irrep of degree 1, so rho decomposes into 3
> # lines.
> irred_decomp_G := IrreducibleDecomposition(rho);
[ rec( basis := [ [ 1, 0, 0 ] ] ), rec( basis := [ [ 0, 1, 0 ] ] ),
 rec( basis := [ [ 0, 0, 1 ] ] ) ]
gap> # The spaces are returned in this format - explicitly keeping the
> # basis - since this basis block diagonalises rho into the irreps,
> # which are the smallest possible blocks. This is more obvious with
> # H.
> irred_decomp_H := IrreducibleDecomposition(tau);
[ rec( basis := [ [ 1, 1, 1 ] ] ),
 rec( basis := [ [ 1, E(3), E(3)^2 ], [ 1, E(3)^2, E(3) ] ] ) ]
gap> # Using the basis vectors given there block diagonalises tau into
> # the two blocks corresponding to the two irreps:
> nice_basis := [ [ 1, 1, 1 ], [ 1, E(3), E(3)^2 ], [ 1, E(3)^2, E(3) ] ];;
gap> tau_diag := ComposeHomFunction(tau, X -> nice_basis^-1 * X * nice_basis);
[ (1,2,3), (1,2) ] -> [ [ [ 1, 0, 0 ], [ 0, E(3), 0 ], [ 0, 0, E(3)^2 ] ],
 [ [ 1, 0, 0 ], [ 0, 0, E(3)^2 ], [ 0, E(3), 0 ] ] ]
</pre></div>

<a id="X87E91CBE7992D126" name="X87E91CBE7992D126"></a>

<h5>5.3-3 IrreducibleDecompositionCollected</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IrreducibleDecompositionCollected</code>( <var class="Arg">rho</var> )</td><td class="tdright">( function )</td></tr></table></div>
Returns: List of lists \(V_i\) of vector spaces \(V_{ij}\) such that \(V = \oplus_i \oplus_j V_{ij}\) and \(V_{ik} \cong V_{il}\) for all \(i\), \(k\) and \(l\) (as representations).

Computes the decomposition of \(V\) into irreducible subrepresentations, grouping together the isomorphic subrepresentations.

<a id="X7C1CF0547D72D354" name="X7C1CF0547D72D354"></a>

<h5>5.3-4 REPN_ComputeUsingSerre</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ REPN_ComputeUsingSerre</code>( <var class="Arg">rho</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A record, in the format described below

This function does all of the computation and (since it is an attribute) saves the results. Doing all of the calculations at the same time ensures consistency when it comes to irrep ordering, block ordering and basis ordering. There is no canonical ordering of irreps, so this is crucial.

<var class="Arg">irreps</var> is the complete list of irreps involved in the direct sum decomposition of <var class="Arg">rho</var>, this can be given in case the default (running Dixon's algorithm) is too expensive, or e.g. you don't want representations over Cyclotomics.

The return value of this function is a record with fields:

<ul>
<li><code class="code">basis</code>: The basis that block diagonalises \(\rho\), see <code class="func">BlockDiagonalBasisOfRepresentation</code> (<a href="chap5_mj.html#X8361AD057AD282AC">5.1-1</a>).

</li>
</ul>

<ul>
<li><code class="code">diagonal_rep</code>: \(\rho\), block diagonalised with the basis above. See <code class="func">BlockDiagonalRepresentation</code> (<a href="chap5_mj.html#X86EB837579C1416D">5.1-2</a>)

</li>
</ul>

<ul>
<li><code class="code">decomposition</code>: The irreducible \(G\)-invariant subspaces, collected according to isomorphism, see <code class="func">IrreducibleDecompositionCollected</code> (<a href="chap5_mj.html#X87E91CBE7992D126">5.3-3</a>)

</li>
</ul>

<ul>
<li><code class="code">centralizer_basis</code>: An orthonormal basis for the centralizer ring of \(\rho\), written in block form. See <code class="func">CentralizerBlocksOfRepresentation</code> (<a href="chap6_mj.html#X7901B6A7860D35C3">6.1-1</a>)

</li>
</ul>
Pass the option <code class="code">parallel</code> for the computations per-irrep to be done in parallel.

Pass the option <code class="code">irreps</code> with the complete list of irreps of \(\rho\) to avoid recomputing this list (could be very expensive)

<div class="example"><pre>
gap> # Does the same thing we have done in the examples above, but all in
> # one step, with as many subcomputations reused as possible
> REPN_ComputeUsingSerre(tau);
rec( basis := [ [ 1, 1, 1 ], [ 1, E(3), E(3)^2 ], [ 1, E(3)^2, E(3) ] ],
 centralizer_basis := [ [ [ [ 1 ] ], [ [ 0, 0 ], [ 0, 0 ] ] ],
 [ [ [ 0 ] ], [ [ 1, 0 ], [ 0, 1 ] ] ] ],
 decomposition := [ [ rec( basis := [ [ 1, 1, 1 ] ] ) ], [ ],
 [ rec( basis := [ [ 1, E(3), E(3)^2 ], [ 1, E(3)^2, E(3) ] ] ) ] ],
 diagonal_rep := [ (1,2,3), (1,2) ] ->
 [ [ [ 1, 0, 0 ], [ 0, E(3), 0 ], [ 0, 0, E(3)^2 ] ],
 [ [ 1, 0, 0 ], [ 0, 0, E(3)^2 ], [ 0, E(3), 0 ] ] ] )
gap> # You can also do the computation in parallel:
> REPN_ComputeUsingSerre(tau : parallel);;
gap> # Or specify the irreps if you have already computed them:
> irreps_H := IrreducibleRepresentations(H);;
gap> REPN_ComputeUsingSerre(tau : irreps := irreps_H);;
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality99%

¤ Dauer der Verarbeitung: 0.20 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.