My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum

LinkBack Thread Tools Display Modes
February 7th, 2019, 09:46 AM   #1
Joined: Feb 2019
From: Earth

Posts: 3
Thanks: 0

Transformation matrix of permutation

I need help with the following:

Let $\displaystyle \sigma \in S_n$ be a permutation of numbers $\displaystyle 1, \dots, n$ and $\displaystyle f:K^n \rightarrow K^n, \begin{pmatrix} x^1 \\ \vdots \\ x^n \end{pmatrix} \mapsto \begin{pmatrix} x^{\sigma(1)} \\ \vdots \\ x^{\sigma(n)} \end{pmatrix}$ a linear mapping.

(i) Calculate the linear transformation matrix $\displaystyle A_\sigma$ of $\displaystyle f$ regarding the standard basis $\displaystyle \{e_1,\dots,e_n\}$ of $\displaystyle K^n$.
(ii) Show that $\displaystyle \mathrm{det}(A_\sigma) = \mathrm{sgn}(\sigma)$.
(iii) Show that $\displaystyle A^{n!} = 1\!\!1$, $\displaystyle 1\!\!1 := \begin{pmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1 \end{pmatrix}$.

(i) $\displaystyle A_\sigma = \begin{pmatrix} e_{\sigma(1)}^T \\ \vdots \\ e_{\sigma(n)}^T \end{pmatrix} = \begin{pmatrix} e_{\sigma(1)} & \cdots & e_{\sigma(n)}\end{pmatrix}$. I'm not sure if I need to show the first equality and how to do it for the second?
(ii) Let $\displaystyle a^i_j$ where $\displaystyle 1 \leq i,j \leq n$ be the $\displaystyle i$th row, $\displaystyle j$th column of matrix $\displaystyle A_\sigma$. We know that $\displaystyle \mathrm{det}(A_\sigma) = \sum_{\pi \in S_n} \mathrm{sgn}(\pi) \cdot a_1^{\pi(1)} \cdot a_2^{\pi(2)} \cdot \ldots \cdot a_n^{\pi(n)}$. [Leibniz formula]
In (i) we see that the $\displaystyle j$th column of $\displaystyle A_\sigma$ is the unit vector $\displaystyle e_{\pi(j)}$, so that $\displaystyle a_1^{\pi(1)} \cdot a_2^{\pi(2)} \cdot \ldots \cdot a_n^{\pi(n)} = 1$ and thus $\displaystyle \mathrm{det}(A_\sigma) = \sum_{\pi \in S_n} \mathrm{sgn}(\pi)$. I don't know how to go from here...
(iii) Matrix multiplication yields $\displaystyle A^2=\begin{pmatrix}
1 & 0 & 0 & \cdots & 0 \\
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1 \end{pmatrix} =: I$. Therefore $\displaystyle A^3$ has $\displaystyle 1$s only in the diagonal and only where $\displaystyle A^1$ already has $\displaystyle 1$s, $\displaystyle 0$s everywhere else. That's all I could figure out...
electron is offline  
February 7th, 2019, 05:05 PM   #2
Senior Member
Joined: Sep 2016
From: USA

Posts: 635
Thanks: 401

Math Focus: Dynamical systems, analytic function theory, numerics
Your description of (iii) is not correct. The symbol 1 in this setting is supposed to denote the identity matrix, not the matrix of all 1s.

How to proceed on these problems also depends a lot on your background. If you have had a first course in group theory then these are all pretty easy. I assume you have already done (i) since it is trivial. I would start with 3 so that once its done you immediately obtain the result that $A$ is invertible and $A^{(n-1)!} = A^{-1}$.

From here, you can easily show that $\left| \left| A \right| \right|_2 \leq 1$ so every eigenvalue of $A$ has absolute value $\leq 1$. But using the result from 3, you have that $A^{-1}$ is also a permutation matrix so its eigenvalues are also bounded by 1. Taken together, you have that every eigenvalue is either 1 or -1 so their product is also. I assume from here you can easily figure out how to determine which value it is.
SDK is offline  

  My Math Forum > College Math Forum > Linear Algebra

matrix, permutation, transformation

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Matrix column permutation Blanco Linear Algebra 1 December 31st, 2015 11:41 AM
Transformation matrix and eigenvalues solrob Linear Algebra 9 September 26th, 2013 10:00 AM
Getting Transformation Matrix tomtong Algebra 0 June 10th, 2013 05:53 PM
Looking for the right transformation matrix Niko Bellic Linear Algebra 5 January 3rd, 2013 11:32 AM
Matrix Transformation aliya Linear Algebra 1 August 10th, 2010 12:39 PM

Copyright © 2019 My Math Forum. All rights reserved.