This is the fourth set of homework problems Link to main web page for the course


For the Sage programs I would like you all to show me your results. After you have finished the programs please email them to me and I will post the solutions. Please include documentation of your function!


Question 1. A column strict tableau of shape $\lambda$ is a filling of the diagram for the partition so the labels of the rows are weakly increasing and the columns are strictly increasing. The algorithm that we discussed in class can be extended so that that any word (that is any sequence of letters) is in bijection with a pair $(P,Q)$ where $P$ is a column strict tableau and $Q$ is a standard tableau. There is no modification of the rule that I described necessary, just ensure that at each step the $P$ tableau (left tableau) is weakly increasing in the rows and strictly increasing in the columns.

EXAMPLE 1: $112233$ is in bijection with the pair of tableau



EXAMPLE 2: $121212$ is in bijection with the pair of tableau



EXAMPLE 3: $332211$ is in bijection with the pair of tableau



If you understand the algorithm and how it works you should be able to determine what message the following pair of tableaux correspond to:


What is the message hidden in the tableaux?
Assuming that this algorithm is a bijection, show that \[ n^m = \sum_{\lambda \vdash m} c_\lambda^n f_\lambda \] where $c_\lambda^n = $ the number of column strict tableaux of shape $\lambda$ and with entries $1,2,3, \ldots, n$.

NB: There is a bit of an error in the tableau and two letters need to be interchanged in the message to get English.

Question 2: Write a function in sage idempotent_decomp( Snalgebraelement ) that takes an element of the symmetric group algebra Snalgebraelement and decomposes it into the basis $e_{i,j}^\lambda$ described in class. That is I would like you to return a list of tuples of the form (mu, i, j, c) such that
sum( c*e_ij_la( mu, i, j ) for (mu, i, j, c) in idempotent_decomp(elt)) == elt is always true for any element of the symmetric group algebra elt.


Hint 1 (mathematics):
If $f = \sum_{\lambda} \sum_{i,j} b_{ij}^\lambda e_{ij}^\lambda$ for some coefficients $b_{rs}^\lambda$, then $$e_{rr}^\lambda \cdot f \cdot e_{ss}^\lambda = b_{rs}^\lambda e_{rs}^\lambda$$

Hint 2 (Sage):
If you want to compute the coefficient $b_{rs}^\mu$ from $g = b_{rs}^\mu e_{rs}^\mu$ then one way of doing this is (if $g \neq 0$) determining the coefficient of a single element in $g$ by the Sage command g.coefficient(g.support()[0]) and then dividing by the coefficient of the same element in $e_{rs}^\mu$ and this can be computed with the command e_ij_la(mu, r, s).coefficient(g.support()[0]).

I ended up solving this question in class in this document and then left the modification of the problem as homework. The function is named eij_decomp( f ) instead of idempotent_decomp as stated in the problem.

Question 3: (modified Question 2 + application) Write a function which converts a matrix in block diagonal form (as in the output of the function SGA_to_matrix( f )) to an element of the symmetric group algebra. That is, write a function matrix_to_SGA( M, n ) such that

matrix_to_SGA( SGA_to_matrix(f), n ) == f
for all elements of f of the symmetric group algebra. Use this function to compute the inverse of the element $(12) + (23) + (34)$ as an element of ${\mathbb Q}[S_4]$