If our polynomial optimization problem has a particular group symmetry, we can do symmetry reduction to get block diagonal matrices. Doing this involves constructing a symmetry-adapted basis. Since symmetry-adapted basis matrices are not unique, I want to know how @blegat constructed a symmetry-adapted basis for the SumOfSquares package. Is there any document at which I can look to see how symmetry-adapted basis is constructed algorithmically?
In the SumOfSquare documentation, it only says how we can define a group symmetry and tell our optimization to have that symmetry. However, it does not mention how Julia finds the symmetric-adapted basis.
Given the action of G on your monomials the action Ļ on the whole monomial basis is induced
For the space of polynomials V (as a vector space with G-action) we compute the character of the (V, G, Ļ) representation
After finding the decomposition of (V, G, Ļ) into irreducibles some symbolic magic in the group ring āG tells us what are the projections onto isotypical summands (that magic is finding the constituent characters which define those projections; sometimes this is followed by finding even tighter minimal projection system)
Given the monomial basis we realize those projections as sparse matrices (only now we start computing with matrices, up to this point everything is symbolic)
unitary vectors in the images of those projections are found via sparse QR decomposition (these basis vectors form the symmetry adapted basis).
I have three questions:
1-
How do you choose unitary vectors from the QR decomposition since if Q is not full rank, the choice will not be unique?
I have read this part of your script:
function image_basis!(
A::AbstractSparseMatrix{T},
::Nothing,
) where {T<:Union{AbstractFloat,Complex}}
F = qr(A)
rk = rank(F)
img = let tmp = F.Q * Matrix(I, size(A, 1), rk)
pinv = getfield(F, :rpivinv)
sparse((@view tmp[pinv, :])')
end
return droptol!(img, _eps(T) * max(size(img)...))
end
But I did not understand how it chooses n=rank(Q) linearly independent columns of Q. Does it choose the first n columns?
2-
If the dimension of irreducible representations (irreps) is greater than 1, then we can decompose to further smaller blocks or, as you said, find tighter projections. How do you find tighter projections? Since the character of an irrep is unique, the projection onto an isotypic component is unique. However, further decomposition is not unique and tighter projections depend on irreps in a matrix form, and we can choose different basis to represent irreps in a matrix form. How do you choose the matrix form of irreps of dimension higher than 1?
3-
There are some books that explain the construction of a symmetry-adapted basis such as Linear Representation of Finite Groups (1977) by Sierre or Group Theoretical Methods and Their Applications (1992) by Fassler & Stiefel. However, these books are old. Since you are an expert in this area, would you tell me which book is appropriate to learn the algorithm you use for symmetry reduction?
The dimension of the image (rank) of the projection is well defined; any (orthogonal) basis of the subspace would do; what we do in the piece of code you quoted is:
compute qr decomposition and obtain its rank rk
the first rk columns from Q are taken as tmp (since Q is not stored directly but rather as a sequence of Hausholder reflections indexing to F.Q is very slow; F.Q*I was the fastest way I found to extract it in Matrix form).
then we just reorder its rows and take sparse representation of the transposed one (so that weāre looking at rows, not columns). The shape of image_basis (i.e. that rank is the number of rows) is a historical choice; probably Iād return basis in columns now, but the first code used rref, so with rows weāre stuck Contributions are welcome
Our implementation of projections is matrix-free. Projections are just idempotent elements (xĀ² = x) in the group algebra āG.
The projection to isotypical component is unique in āG, but not as an element of End((V, G, Ļ)) i.e. as a matrix: a matrix representation of a projection is already a choice of (projection, basis). Itās the same difference as linear operator vs matix.
Tighter projections use a lemma of Schur that (over an algebraically closed field) the commutant of matrix algebra (here: matrix algebra defined by the linear representation of the finite group) consist of particularly simple matrices:
they are direct sums of endomorphisms of isotypical subspaces (i.e. isotypical subspaces are orthogonal which gives us block structure for endomorphisms, this holds also for non-algebraically closed field where the exponent of the group is invertible)
within isotypical subspace (of character Ļ) the endomorphisms are of the form MāIā, where n = degree(Ļ) and M is (square) of size multiplicity(Ļ, action_character(V, G, Ļ)). So in the end only mĀ² parameters are needed for reconstructing the whole endomorphism; For every irreducible character Ļ± we try to find a (non-central) projection pįµØ such that Ļ±āpįµØ is of possible low rank (desirably 1). We call those {Ļ±āpįµØ}_{Ļ± ā Ä} a minimal projection system. Sometimes it exists (symmetric, alternating groups etc.) sometimes it doesnāt (real representations of cyclic groups).
For specific groups and specific representations other methods are possible (e.g. @dlfivefifty in NumericalRepresentationTheory uses Murphys idempotents paired with explicit description of reps by Young Tableaux, but maybe he can say something more about the method
I think all of this stuff about irreducibles can be found in the book by Serre (or any textbook on representation theory). The formulation of the minimal projection is nothing particularly deep, but maybe requires you to work a bit longer with group algebras. A somewhat condensed account of what weāre doing is presented in sections 2 (theory) and 3.3 (particular computations) of an old paper of mine.
I donāt know the other book you mentioned, but it does looks very interesting!
Kind words I just happened to be the first who needed a well rounded package to do all of this. If that makes me an expert, thatās even better
Hi again Marek @abulak ,
Does your Julia package provide a symmetry-adapted basis for any finite group? Does this package decompose G-representations that some of the real irreducible representations of G are quaternion-type? Like the group Q8 for instance?
For a real representation V, we have its projection onto its isotypic component (W_i^{n_i}), allowing us to construct symmetry-adapted bases for the projection of End_G(V) onto End_G(W_i^{n_i}). Each block corresponding to isotypic components can be further block-diagonalized. Specifically: If W_i is a real-type, those small blocks have size n_i \times n_i, if W_i is complex-type, those small blocks have size 2n_i \times 2n_i, and if W_i is quaternion-type, those small blocks have size 4n_i \times 4n_i.
I am wondering if the symmetry-adapted basis provided by your package can fully block-diagonalize in the quaternion case, or if it only block-diagonalizes up to the blocks corresponding to the isotypic components. Let me ask you this way, if a quaternion-type representation W appears n times in a representation, does your Julia package provide a symmetry-adapted basis such that the block corresponding to W^n has dim(W) identical blocks of size 4n \times 4n?
That depends on what do you request as coefficients in Wedderburn decomposition. If You ask that the basis is real (e.g. by asking for Float64 coefficients), then the isotypical projections computed (in the group ring) correspond to real affordable characters. if you pass e.g. ComplexF64, then the projections will correspond to complex characters.
(Iām not sure if the quaternionic characters will be handled correctly ā please test and report!).
In either case the minimal projections (as a product of a character and a rational-valued function on the group) will be computed and realized as matrices with coefficients depending on what have been specified at the very beginning.
Have a look at the docstring.
E.g. for complex characters there definitely will not be \dim(W) blocks of size 2n Ć 2n as that would be way too large What is going to happen is that two āconjugateā complex-irreducible blocks merge to a single real-irreducible block of double the dimension. Therefore for `W_i' = W_i \oplus \overline{W_i} we have n_i' = n_i, but \dim W_i' = 2\dim W_i.
I think I understand your argument. I made a mistake I meant \frac{\dim(W)}{2} blocks of size 2n \times 2n. Indeed it is the smallest possible decomposition. It is possible that we use different notations. Here, I consider W to be a complex-type real irreducible representation. That means there exist two non-isomorphic irreducible representations W_0 and W_0^* over complex numbers such that W \otimes_{\mathbb{R}} \mathbb{C}=W_0 \oplus W_0^*. However, it seems by W you mean irreducible representation over complex numbers such that W is not realizable over real numbers. If this is the case, so we both have the same opinion.
So please consider W to be a complex-type real irreducible representation. Here dimension of W^n is n \dim(W). If I choose a symmetry-adapted basis using complex numbers, then I get \dim(W) blocks of size n \times n. As you mentioned we can merge two conjugate complex blocks into one real block. Consequently, by choosing a symmetry-adapted basis using real numbers, we get \frac{\dim(W)}{2} blocks of size 2n \times 2n. If we agree up to this point so with a similar argument using the properties of characters, we can extend this to a quaternion-type real irreducible representation W. In this case, by choosing a symmetry-adapted basis, we get \frac{\dim(W)}{4} blocks of size 4n \times 4n. Indeed, one can say for a real irreducible representation W, a symmetry-adapted basis gives \frac{\dim(W)}{\dim(End_G(W))} blocks of size n\dim(End_G(W)) \times n\dim(End_G(W)).
If I want to check that everything works properly, I need to use a group having a quaternion-type real irreducible representation such that \dim(W) > \dim(End_G(W)). It is quite hard since the smallest group with this property is the binary octahedral group with size 48. I cannot check that. I also have not seen any book or paper that shows we can construct a symmetry-adapted basis in this case. For real-type W, we can construct a projection from W^n onto \text{Hom}_G(W,W^n) using any orthogonal realization of W. However, It is not straightforward to extend this to complex or quaternion-type W. I appreciate if you take a look at this:
I have also tried to email you, but your kit.edu email does not exist.
Yes, that email is no more, as I donāt work there. Why they terminate 2 months after the contract and do not allow any redirection is a question too big for my little head
When you talk about representations of real, complex or quaternionic type do you mean the +1, 0, or -1 value of the Frobenius-Schur indicator?
Just to be sure, when you write \dim W do you mean real or complex dimension?
Note that Dixsons algorithm computes complex-irreducible characters (and with them their isotypical projections). If a user asks for a real symmetry adapted basis, then we need to work out which complex-irreducible characters to combine to obtain a complete set of real-irreducibles.
I always believed that the complex-type irreducible over \mathbb{C} characters correspond to representations not realizable over real numbers. So when encountering a character (say \chi) like this we need to pass to its double cover real and \mathbb{R}-irreducible character \chi' = \chi + \overline \chi to obtain a projection to real-isotypical submodule.
Analogously, for a irreducible over \mathbb{C}, real valued character of quaternionic type the computed matrix projection will live over the field specified by the user by the action. So I believe no additional steps need to be taken in this case. Please correct me if Iām wrong here!
Why canāt you examine the action of G on itself? Are you solving a particular problem where these representations show up, or is this just a question of curiosity (i.e. youāre trying to prove a theorem?)
I mean dimension over the ground field. So if I consider W to be a complex irrep, \dim(W) means dimension over \mathbb{C}, if I say W is a real irrep, \dim(W) means the dimension over \mathbb{R}. When I say complex-type irrep, I mean a real irrep with Schur indicator 0. So when W is a complex-type irrep, I consider the ground field to be \mathbb{R}, and \dim(W) is the dimension over \mathbb{R} here.
We just have a different definition. By a complex-type irrep, I mean a real irrep with Schur indicator 0.
Yes. I have not seen any theory for constructing symmetry-adapted bases when our real representation involves quaternion-type irreps. That is when some real irrep with Schur indicator -1 appear in the decomposition of a real representation into irreducible irreps.
If the real irrep W is of real-type (Schur indicator 1), complex-type (Schur indicator 0), or quaternion-type (Schur indicator -1), then \dim(\text{End}_G(W)) over \mathbb{R} is 1, 2, or 4, respectively. Theory states that the projection of our representation \rho onto the isotypic component corresponding to W is
Here, \chi_W denotes the character of W with the consideration that the ground field is \mathbb{R}. Using this projection, we can construct a symmetry-adapted basis that block diagonalizes to a certain extent, although it does not provide the further smaller blocks. To achieve further block diagonalization, we need to satisfy the condition \dim(W) > \dim(\text{End}_G(W)). This is because each block can be block-diagonalized into \frac{\dim(W)}{\dim(\text{End}_G(W))} identical blocks of size: (number of times W appears in \rho) \times \dim(\text{End}_G(W)). Therefore, if \dim(W) = \dim(\text{End}_G(W)), the block corresponding to the isotypic component cannot be further block-diagonalized. Note that \dim(W) is always a multiple of \dim(\text{End}_G(W)). For example, if W has a Schur indicator of -1, then \dim(W) is a multiple of 4.
My problem arises from the fact that I have not encountered a theory that can find those smaller blocks when W has a Schur indicator of -1. Hereās why: If the Schur indicator of W is 1, we can project onto a smaller subrepresentation (smaller than isotypic components). In this case, if R_W is an orthogonal realization of W, where each R_W(g) is an orthogonal matrix with entries [R_W(g)]_{i,j}, then one can define an orthogonal projection from \rho onto the subrepresentation corresponding to the smallest possible blocks as follows:
This holds true only when W has a Schur index of 1 because only in this case is W also irreducible when the field is extended from \mathbb{R} to \mathbb{C}. In other words, only in this case is W \otimes_{\mathbb{R}} \mathbb{C} a complex irrep. This is crucial for the following reason: consider [R_W]_{i,i}: G \to \mathbb{R} as a function from groups to the reals. Only when W \otimes_{\mathbb{R}} \mathbb{C} is a complex irrep does
\frac{\dim(W)}{|G|}\sum_{g \in G}[R_W(g^{-1})]_{i,i}[R_W(g^{-1})]_{j,j} = 0 \text{ for } i \ne j.
When W has a Schur indicator of 0, we may not be able to use such a projection. Instead, we work over the field of complex numbers, where we can merge any complex block into a real block of double size, because for every complex block, its conjugate is another complex block.
Now, I am curious how one can achieve the smallest possible block diagonalization when irreps with a Schur indicator of -1 appear. Generally, groups that have real irreps with a Schur indicator of -1 are rare. The smallest one is the quaternion group of dimension 8. In this case, everything works because for the real irrep W with a Schur indicator of -1, \dim(W) = \dim(\text{End}_G(W)) = 4, so we do not need to further block-diagonalize the block corresponding to the isotypic component of W. However, if I want a group with a real irrep having a Schur indicator of -1 such that \dim(W) > \dim(\text{End}_G(W)), I need to choose the binary octahedral group of size 48. This is the smallest example where the real irrep W with a Schur indicator of -1 has \dim(W) = 8 and \dim(\text{End}_G(W)) = 4.
I vaguely understand what you want to achieve, but honestly speaking this seems to be out of scope of SymbolicWedderburn.jl. The point of this package is precisely to not work with orthogonal realization R_W, but perform as much of computations symbolically in the group algebra without resorting to matrix calculations. Do you envision using those formulas effectively when the dimension of the big representation is in millions?
I suggested this above, but let me repeat: why donāt you work with binary octahedral group acting on itself? itās just a 48-dimensional (regular) representation, surely you can work out the isotypic of quaternionic type inside?
In general, we do not have a single symmetry-adapted basis; there are potentially infinitely many, particularly when the isotypic components are not simple. Am I correct?
I understand you use sparse QR factorization to select a āsparseā symmetry-adapted basis. However, even with this method, different bases can be constructed, which essentially involves choosing an orthogonal basis for irreducible representations (irreps).
When working with group algebras to find some idempotent elements, we also need to select an orthogonal basis. I am aware that the primitive central idempotents in the group algebra can be determined using characters. These idempotents correspond to the projection of our representation onto the isotypic components. However, for further block diagonalization, we need to identify idempotent elements that are not central. As far as I know, these non-central idempotents can be constructed based on the entries of matrices corresponding to irreps with respect to an orthogonal basis.
For example, if an irreducible \mathbb{C}-representation is given in matrix form (r_{i j}(g)) with respect to an orthogonal basis, then
e_{ii}=\frac{\dim_{\mathbb{C}}(W)}{|G|} \sum_{g \in G} r_{ii}(g^{-1}) g
are (non-central) idempotent elements in \mathbb{C}G. Additionally, they are mutually orthogonal.
Now, I am wondering how it is possible to construct a symmetry-adapted basis without choosing a basis for irreps.
the QR we do is very sparse and already very low rank, thatās why itās very fast. Actually the most time consuming part is extracting rows/columns of Q from Hausholder reflections stored in the decomposition.
But very low rank comes from the fact that the projections are (hopefully) already minimal. And we do it by searching for non-central idempotents in the group algebra. Itās a heuristic algorithm based on my intuition of monomial representations and (somewhat to my surprise) it works very well in practice.
Can you translate your formula to to group algebra? The problem is to compute r_{i,j} from a character and the action. To me this seems a very hard questionā¦
But maybe you do have some good ideas here! please share!
Thatās true, there are many choices for the bases, but all of them will be equivalent for our purposes. What we need is āthe sameā single unit vector from each irreducible submodule W \subset \oplus_{i=1}^n W_i (irrep on the left, isotypical on the right). By working in the group algebra we avoid even realizing the right side, not to mention computing the orthogonal decomposition.
I feel that we have developed a mutual understanding, allowing me to share my thoughts more concisely. We both look for non-central idempotents. They should be mutually orthogonal.
What do you mean? It is indeed in the language of group algebra. R is a matrix realization of K-irrep W. That means R: G \to GL(K^{\dim_K(W)}). R(g) is a matrix for each g \in G. Its (i,j) entries is r_{ij}(g). We can view r_{ij}:G \to K functions from G to the underlying field. Therefore, \sum_{g \in G}r_{ij} (g^{-1})g is an element in the group algebra KG. Now, if K=\mathbb{C} and R is an orthogonal realization of W, then
are the desired idempotents. Here, the key fact is we know e_{ii} are mutually orthogonal because of the orthogonality relation between r_{ii}(g). Since the character of W is the trace of R(g), that is \chi_W(g)= \sum_{i=1}r_{ii}(g), then \sum_ie_{ii} is indeed a primitive central idempotent of \mathbb{C}G.
Now, how do you find your idempotent elements, and how do you know they are mutually orthogonal?? Which theory do you use to ensure you get orthogonal idempotents? Moreover, how do you know the idempotent that you get cannot be decomposed to a sum of two orthogonal idempotents? I have not seen these theories in your papers. Am I missing something?
In much the same way we have the characters, we have r_{ij}. It does not relate to our representation or how our group acts. I mean r_{ij} are independent of our representation. Each group has some particular irreducible representations. Each irrep has its own character and its own r_{ij}. The former is independent of the choice of basis for that irrep, but the latter is dependent on the choice of basis.
There is no need to realize the isotypic components. I have never said that. Each irrep is given to us in the form of a table. Isnāt it? We have r_{ij} from the table.
Now, would you tell me how you find your idempotents elements in the group algebra so that they are mutually orthogonal?
I am asking this because although I know how to find those idempotents in \mathbb{C}G, I do not know how to find them in \mathbb{R}G in particular when G has real irrep with Schur indicator 0 and 1.
Computing character table is very easy and can be done in a blink of a second given group generators. I donāt know an algorithm that computes r_{ij}:G ā K from the corresponding character \chi and and an action of G on a vector space V (equivalently: a representation \rho\colon G ā Aut(V) which contains \chi as a subrepresentation).
Let me make this very precise. I have only this input at my disposal:
finite group G with an explicit set of generators
action of G on V
You additionally assume the access to function(s) r_{ij}\colon G ā K that gives you access to individual elements of an image of irreducible matrix representation.
I donāt know how to compute such function from the input only. If you have ideas leading in this direction, Iād be very happy to hear.
Which papers did you read? This particular bit is mentioned here, in Section 2.3, youāll find the definition of minimal projection system there. In short, there we donāt need all of primitive (non-central) idempotents, we need just one for each character maybe this makes it easier for us?
Answering a question at the end of your previous post:
That is precisely the aim of SymbolicWedderburn.jl
Let me ask you a straightforward question. This will help me a lot to understand the difference between your way of finding symmetry adapted basis and my understanding. I would appreciate it if you answered this.
Suppose G is the binary octahedral group. G has 8 real irreps, namely W_1,\cdots, W_8. Let d_i=\dim_{\mathbb{R}}(W_i), k_i =\dim_{\mathbb{R}}({\text{End}_G(W_i)}), and \nu_i be Frobinus-Schur indicator of W_i.
We have the following table:
Suppose our representation V has the decomposition V= W_1^2 \oplus W_2^2 \oplus W_3^2 \oplus W_4^2 \oplus W_5^2 \oplus W_6^2 \oplus W_7^2 \oplus W_8^2. Would you tell me using your theory what is the dimension of each block after symmetry reduction of symmetric (self-adjoint) elements of End_G(V)? (Would you just answer the three following questions at the bottom?)
The block corresponding to W_1^2 contains one 2 \times 2 block.
The block corresponding to W_2^2 contains one 2 \times 2 block.
The block corresponding to W_3^2 contains two 2 \times 2 identical blocks.
The block corresponding to W_4^2 contains three 2 \times 2 identical blocks.
The block corresponding to W_5^2 contains three 2 \times 2 identical blocks.
The block corresponding to W_6^2 contains how many identical blocks of which size?
The block corresponding to W_7^2 contains how many identical blocks of which size?
The block corresponding to W_8^2 contains how many identical blocks of which size?
Contributions are welcome 