Abstract Nonsense

Crushing one theorem at a time

Halmos Section 26 and 27: Permutations and Cycles cont.


Point of post: This is a continuation of this post.

Continue reading

Advertisements

November 10, 2010 Posted by | Fun Problems, Halmos, Linear Algebra, Uncategorized | , , , , , , | Leave a comment

Permutations (Pt. VI Alternate Definitions of the Sign of a Permutation cont.)


Point of post: This is a literal continuation of this post. I just hate when that dark grey to light grey thing happens. Just pretend that there was no lapse in the posts

And so we continue…

Continue reading

November 8, 2010 Posted by | Algebra, Halmos, Linear Algebra | , , , , , | 1 Comment

Permutations (Pt. III Orbits and Cycles cont.)


Point of post: This post is a literal continuation of this post in the sense that if it weren’t for size constraints these two posts would be one. So, think of this as just the “next page” of that post.

\text{ }

Motivation

Recall from the last post that for any \pi\in S_n we have that [n] can be partitioned into orbits \left\{\mathcal{O}_1,\cdots,\mathcal{O}_m\right\}. Notice though that each of these orbits induces an element of S_n namely each \mathcal{O}_k induces \pi_k\in S_n given by

\text{ }

\pi_k(x)=\begin{cases}\pi(x) & \mbox{if}\quad x\in\mathcal{O}_k\\ x & \mbox{if}\quad x\notin\mathcal{O}_k\end{cases}

\text{ }

Permutations of this kind are going to be the archetype for the sought class of permutations we have been searching for (see the motivation of the last post if your confused). These are going to be the archetypes of cycles. Which we will now rigorously define.

Continue reading

November 7, 2010 Posted by | Algebra, Group Theory | , , , | 3 Comments

Permutations (Pt. III Orbits and Cycles)


Point of post: In this post we continue the discussion of permutations discussed here and here in our journey to understand permutations rigorously, clearly, and fully so that we may discuss the basics of multilinear forms as is told in Halmos’s book. In it we will discuss the ideas of orbits and their ilk, cycles.

Remark: Because of the amount of information that will go into this “post”, I will have to break it into two smaller posts. I chose not to break orbits and cycles into separate posts unto themselves since they are inextricably linked (at least in the context we’re viewing them in).

Motivation

It is common place in mathematics to take concepts and try to ascertain what is the most fundamental way to describe them. For topological spaces we have subbases, for vector spaces we have bases, for groups we have generators. Permutations are no different. We are looking for some fundamental, easily described, class of permutations such that every permutation can be written as a product (compostion) of such matrices. We shall begin our discussion with a few brief conventions on notation Next we will define orbits which we shall see are in essence partitions [n] induced by a permutation \pi. From there we will use this idea of orbits to define cycles which shall be the fundamental types of permutation of which all permutations are composed of.

Continue reading

November 6, 2010 Posted by | Algebra, Halmos, Linear Algebra, Uncategorized | , , , , | 1 Comment

Permutations (Pt. II Permutation Matrices)


Point of post: This post is a continuation of this post in a continuing effort to define permutations fully and clearly, something someone reading Halmos’s book is bounded not to get (though admittedly this isn’t his goal). In this particular post we discuss the interesting concept of “permutation matrices” in an effort to intuitively simplify proofs covered in the next few posts.

Motivation

Often in mathematics the simple concept of “thinking of something differently” can have a profound impact on a study. The study of permutations is no different. Thus, it is clearly fruitful to search of as many different ways as possible. In this post we take permutations and think about them in terms of something most of us know all about, matrices.

Continue reading

November 6, 2010 Posted by | Algebra, Halmos, Linear Algebra | , , , , | 3 Comments

Permutations (Pt. I)


Point of post: This will be the first of a few posts that are an expansion upon the topic of permutations discussed in Halmos sections 26, 27, and 28. I expand not because it’s a necessity for the material he covers, but because I think it’s a fruitful topic to explore considering it’s vast use througout many fields of mathematics.

Motivation

No doubt any reader familiar with even the most basic group theory is aware of the power of permutations, in their own right, but alas this being a post about linear algebra I’ll try to keep the group theoretic rhetoric to a minimum. Anyways, why would anyone doing linear algebra care about permutations? Well, let’s recall some basics from undergraduate linear algebra, namely the determinant function. If one recalls the determinant function is some mystic tool which gives qualitative measure to the invertability of a matrix

M_n=\begin{bmatrix} a_{1,1} & \cdots & a_{1,n}\\ \vdots & \ddots & \vdots\\ a_{n,1} & \cdots & a_{n,n}\end{bmatrix}

namely, M is invertible if and only if \det M\ne 0.  But, how exactly did we define \det M? Well, for two-by-two matrices it was simple

\det M_2=a_{1,1}a_{2,2}-a_{1,2}a_{2,1}

If you have really good memory you might even remember off the top of your head \det M_3 (I sure can’t, I have to do the juxtaposition of a copy of the matrix trick). They then told you that the general form of the determinant was the ugly beast of the formua

\displaystyle \det M_n=\sum_{\pi\in S_n}\text{sgn}(\pi)\prod_{j=1}^{n}a_{j,\pi(j)}

and so we see the first (of trust me many) appearances of the concept of permutation and its ilk. But, that’s matrix theory you say! Why should a tangentially related concept motivate us to study this topic? Well, two reasons. Firstly, even though the determinant is classically matrix theory as we will see in subsequent chapters the determinant will play a vital role in determining the invertibility of a linear transformation, something which hits us very, very close to home. But, more immediately the determinant interests as as it is a an archetypal example of something we shall soon study. In particular if thought of as a function of the columns it is really a function

\det:\mathbb{C}^n\to\mathbb{C}

which is linear in each variable. In other words it’s the n-fold analogue of a bilinear form, it’s a k-linear form. Moreover, it has the property that if \bold{z}_1,\cdots,\bold{z}_n\in\mathbb{C}^n that

\det(\bold{z}_1,\cdots,\bold{z}_n)=\text{sgn}(\pi)\det(\bold{z}_{\pi(1)},\cdots,\bold{z}_{\pi(n)})

which is  an example of something called a skew-symmetric form. Both of these are integral parts of the subject, to be introduced, called multilinear algebra. So, with that said let’s embark on our study of the permutations, their group, and their parity.

Continue reading

November 6, 2010 Posted by | Algebra, Halmos, Linear Algebra | , , , | 4 Comments