Definition 9.1.1. Fix n ∈ ℕ. Then, for each f ∈_n, we associate an n × n matrix, denoted P^f = [p_ij], such that p_ij = 1, whenver f(j) = i and 0, otherwise. The matrix P^f is called the Permutation matrix corresponding to the permutation f. For example, I₂, corresponding to Id₂, and = E₁₂, corresponding to the permutation (1,2), are the two permutation matrices of order 2 × 2.

Remark 9.1.2. Recall that in Remark 9.2.16.1, it was observed that each permutation is a product of n transpositions, (1,2),…,(1,n).

1.

Verify that the elementary matrix E_ij is the permutation matrix corresponding to the transposition (i,j) .

2.

Thus, every permutation matrix is a product of elementary matrices E_1j, 1 ≤ j ≤ n.

3.

For n = 3, the permutation matrices are I₃, = E ₂₃ = E₁₂E₁₃E₁₂, = E ₁₂, = E ₁₂E₁₃, = E ₁₃E₁₂ and = E ₁₃.

4.

Let f ∈ _n and P^f = [p_ij] be the corresponding permutation matrix. Since p_ij = δ_i,j and {f(1),…,f(n)} = [n], each entry of P^f is either 0 or 1. Furthermore, every row and column of P^f has exactly one nonzero entry. This nonzero entry is a 1 and appears at the position p_i,f(i).

5.

By the previous paragraph, we see that when a permutation matrix is multiplied to A DRAFT

(a)

from left then it permutes the rows of A.

(b)

from right then it permutes the columns of A.

6.

P is a permutation matrix if and only if P has exactly one 1 in each row and column.
Solution: If P has exactly one 1 in each row and column, then P is a square matrix, say n×n. Now, apply GJE to P. The occurrence of exactly one 1 in each row and column implies that these 1’s are the pivots in each column. We just need to interchange rows to get it in RREF. So, we need to multiply by E_ij. Thus, GJE of P is I_n and P is indeed a product of E_ij’s. The other part has already been explained earlier.

Theorem 9.1.3. Let A and B be two matrices in RREF. If they are row equivalent then A = B.

Definition 9.2.1. For a positive integer n, denote [n] = {1,2,…,n}. A function f : A → B is called

1.

one-one/injective if f(x) = f(y) for some x,y ∈ A necessarily implies that x = y.

2.

onto/surjective if for each b ∈ B there exists a ∈ A such that f(a) = b.

3.

a bijection if f is both one-one and onto.

Example 9.2.2. Let A = {1,2,3}, B = {a,b,c,d} and C = {α,β,γ}. Then, the function

1.

j : A → B defined by j(1) = a,j(2) = c and j(3) = c is neither one-one nor onto.

2.

f : A → B defined by f(1) = a,f(2) = c and f(3) = d is one-one but not onto.

3.

g : B → C defined by g(a) = α,g(b) = β,g(c) = α and g(d) = γ is onto but not one-one.

4.

h : B → A defined by h(a) = 2,h(b) = 2,h(c) = 3 and h(d) = 1 is onto.

5.

h ∘ f : A → A is a bijection. DRAFT

6.

g ∘ f : A → C is neither one-one not onto.

Remark 9.2.3. Let f : A → B and g : B → C be functions. Then, the composition of functions, denoted g ∘ f, is a function from A to C defined by (g ∘ f)(a) = g(f(a)). Also, if

1.

f and g are one-one then g ∘ f is one-one.

2.

f and g are onto then g ∘ f is onto.

Thus, if f and g are bijections then so is g ∘ f.

Definition 9.2.4. A function f : [n] → [n] is called a permutation on n elements if f is a bijection. For example, f,g : [2] → [2] defined by f(1) = 1,f(2) = 2 and g(1) = 2,g(2) = 1 are permutations.

Exercise 9.2.5. Let ₃ be the set consisting of all permutation on 3 elements. Then, prove that ₃ has 6 elements. Moreover, they are one of the 6 functions given below.

1.

f₁(1) = 1,f₁(2) = 2 and f₁(3) = 3.

2.

f₂(1) = 1,f₂(2) = 3 and f₂(3) = 2.

3.

f₃(1) = 2,f₃(2) = 1 and f₃(3) = 3. DRAFT

4.

f₄(1) = 2,f₄(2) = 3 and f₄(3) = 1.

5.

f₅(1) = 3,f₅(2) = 1 and f₅(3) = 2.

6.

f₆(1) = 3,f₆(2) = 2 and f₆(3) = 1.

Remark 9.2.6. Let f : [n] → [n] be a bijection. Then, the inverse of f, denote f^-1, is defined by f^-1(m) = ℓ whenever f(ℓ) = m for m ∈ [n] is well defined and f^-1 is a bijection. For example, in Exercise 9.2.5, note that f_i^-1 = f_i, for i = 1,2,3,6 and f₄^-1 = f₅.

Remark 9.2.7. Let _n = {f : [n] → [n] : σ is a permutation}. Then, _n has n! elements and forms a group with respect to composition of functions, called product, due to the following.

1.

Let f ∈ S_n. Then,

(a)

f can be written as f = , called a two row notation.

(b)

f is one-one. Hence, {f(1),f(2),…,f(n)} = [n] and thus, f(1) ∈ [n],f(2) ∈ [n] \{f(1)},… and finally f(n) = [n] \{f(1),…,f(n - 1)}. Therefore, there are n choices for f(1), n- 1 choices for f(2) and so on. Hence, the number of elements in _n equals n(n - 1)2 ⋅ 1 = n!.

2.

By Remark 9.2.3, f ∘ g ∈_n, for any f,g ∈ S_n.

3.

Also associativity holds as f ∘ (g ∘ h) = (f ∘ g) ∘ h for all functions f,g and h.

4.

_n has a special permutation called the identity permutation, denoted Id_n, such that Id_n(i) = i, for 1 ≤ i ≤ n. DRAFT

5.

For each f ∈_n, f^-1 ∈_n and is called the inverse of f as f ∘ f^-1 = f^-1 ∘ f = Id_n.

Lemma 9.2.8. Fix a positive integer n. Then, the group _n satisfies the following:

1.

Fix an element f ∈_n. Then, _n = {f ∘ g : g ∈_n} = {g ∘ f : g ∈_n}.

2.

_n = {g^-1 : g ∈_n}.

Definition 9.2.9. Let f ∈_n. Then, the number of inversions of f, denoted n(f), equals

Example 9.2.10.

1.

For f = , n(f) = |{(1,2),(1,3),(2,3)}| = 3.

2.

In Exercise 9.2.5, n(f₅) = 2 + 0 = 2.

3.

Let f = . Then, n(f) = 3+1+1+1+0+3+2+1 = 12.

Definition 9.2.11. [Cycle Notation] Let f ∈ _n. Suppose there exist r,2 ≤ r ≤ n and i₁,…,i_r ∈ [n] such that f(i₁) = i₂,f(i₂) = i₃,…,f(i_r) = i₁ and f(j) = j for all j≠i₁,…,i_r. Then, we represent such a permutation by f = (i₁,i₂,…,i_r) and call it an r-cycle. For example, f = = (1,4,5) and = (2,3).

Remark 9.2.12.

1.

One also write the r-cycle (i₁,i₂,…,i_r) as (i₂,i₃,…,i_r,i₁) and so on. For example, (1,4,5) = (4,5,1) = (5,1,4). DRAFT

2.

The permutation f = is not a cycle.

3.

Let f = (1,3,5,4) and g = (2,4,1) be two cycles. Then, their product, denoted f ∘ g or (1,3,5,4)(2,4,1) equals (1,2)(3,5,4). The calculation proceeds as (the arrows indicate the images):
1 → 2. Note (f ∘ g)(1) = f(g(1)) = f(2) = 2.
2 → 4 → 1 as (f ∘ g)(2) = f(g(2)) = f(4) = 1. So, (1,2) forms a cycle.
3 → 5 as (f ∘ g)(3) = f(g(3)) = f(3) = 5.
5 → 4 as (f ∘ g)(5) = f(g(5)) = f(5) = 4.
4 → 1 → 3 as (f ∘ g)(4) = f(g(4)) = f(1) = 3. So, the other cycle is (3,5,4).

4.

Let f = (1,4,5) and g = (2,4,1) be two permutations. Then, (1,4,5)(2,4,1) = (1,2,5)(4) = (1,2,5) as 1 → 2,2 → 4 → 5,5 → 1,4 → 1 → 4 and
(2,4,1)(1,4,5) = (1)(2,4,5) = (2,4,5) as 1 → 4 → 1,2 → 4,4 → 5,5 → 1 → 2.

5.

Even though is not a cycle, verify that it is a product of the cycles (1,4,5) and (2,3).

Definition 9.2.13. A permutation f ∈_n is called a transposition if there exist m,r ∈ [n] such that f = (m,r).

Remark 9.2.14. Verify that

1.

(2,4,5) = (2,5)(2,4) = (4,2)(4,5) = (5,4)(5,2) = (1,2)(1,5)(1,4)(1,2).

2.

in general, the r-cycle (i₁,…,i_r) = (1,i₁)(1,i_r)(1,i_r-1)(1,i₂)(1,i₁).

3.

So, every r-cycle can be written as product of transpositions. Furthermore, they can be written using the n transpositions (1,2),(1,3),…,(1,n).

Theorem 9.2.15. Let f ∈_n. Then, f can be written as product of transpositions.

Remark 9.2.16. Note that when one writes a permutation as product of disjoint cycles, cycles of length 1 are suppressed so as to match Definition 9.2.11. For example, the algorithm in the proof of Theorem 9.2.15 implies

1.

Using Remark 9.2.14.3, we see that every permutation can be written as product of the n transpositions (1,2),(1,3),…,(1,n).

2.

= (1)(2,4,5)(3) = (2,4,5).

3.

= (1,4,5)(2)(3)(6,9)(7,8) = (1,4,5)(6,9)(7,8).

Lemma 9.2.17. Suppose there exist transpositions f_i,1 ≤ i ≤ t, such that

Theorem 9.2.18. Let f ∈_n. If there exist transpositions g₁,…,g_k and h₁,…,h_ℓ with

Definition 9.2.19. [Even and Odd Permutation] A permutation f ∈_n is called an

1.

even permutation if f can be written as product of even number of transpositions.

2.

odd permutation if f can be written as a product of odd number of transpositions.

Definition 9.2.20. Observe that if f and g are both even or both odd permutations, then f ∘g and g ∘f are both even. Whereas, if one of them is odd and the other even then f ∘g and g ∘ f are both odd. We use this to define a function sgn : _n →{1,-1}, called the signature of a permutation, by DRAFT

Example 9.2.21. Consider the set _n. Then,

1.

by Lemma 9.2.17, Id_n is an even permutation and sgn(Id_n) = 1.

2.

a transposition, say f, is an odd permutation and hence sgn(f) = -1

3.

using Remark 9.2.20, sgn(f ∘ g) = sgn(f) ⋅ sgn(g) for any two permutations f,g ∈_n.

Definition 9.2.22. Let A = [a_ij] be an n×n matrix with complex entries. Then, the determinant of A, denoted det(A), is defined as

(9.2.2)

For example, if ₂ = {Id,f = (1,2)} then for A = , det(A) = sgn(Id) ⋅ a_1Id(1)a_2Id(2) + sgn(f) ⋅ a_1f(1)a_2f(2) = 1 ⋅ a₁₁a₂₂ + (-1)a₁₂a₂₁ = 1 - 4 = -3.

Theorem 9.3.1 (Properties of Determinant). Let A = [a_ij] be an n × n matrix.

1.

If A[i,:] = 0^T for some i then det(A) = 0.

2.

If B = E_i(c)A, for some c≠0 and i ∈ [n] then det(B) = cdet(A). DRAFT

3.

If B = E_ijA, for some i≠j then det(B) = -det(A).

4.

If A[i,:] = A[j,:] for some i≠j then det(A) = 0.

5.

Let B and C be two n×n matrices. If there exists m ∈ [n] such that B[i,:] = C[i,:] = A[i,:] for all i≠m and C[m,:] = A[m,:] + B[m,:] then det(C) = det(A) + det(B).

6.

If B = E_ij(c), for c≠0 then det(B) = det(A).

7.

If A is a triangular matrix then det(A) = a₁₁a_nn, the product of the diagonal entries.

8.

If E is an n × n elementary matrix then det(EA) = det(E)det(A).

9.

A is invertible if and only if det(A)≠0.

10.

If B is an n × n matrix then det(AB) = det(A)det(B).

11.

If A^T denotes the transpose of the matrix A then det(A) = det(A^T ).

Remark 9.3.2.

1.

As det(A) = det(A^T ), we observe that in Theorem 9.3.1, the condition on “row” can be replaced by the condition on “column”.

2.

Let A = [a_ij] be a matrix satisfying a_1j = 0, for 2 ≤ j ≤ n. Let B = A(1|1), the submatrix of A obtained by removing the first row and the first column. Then det(A) = a₁₁ det(B).
Proof: Let σ ∈_n with σ(1) = 1. Then, σ has a cycle (1). So, a disjoint cycle representation of σ only has numbers {2,3,…,n}. That is, we can think of σ as an element of _n-1. Hence,

Theorem 9.3.3. Let A be an n × n matrix. Then, det(A) = ∑ _j=1ⁿ(-1)^1+ja_1j detA(1|j), where recall that A(1|j) is the submatrix of A obtained by removing the 1^st row and the j^th column.

Theorem 9.4.1. Let V be a finite dimensional vector space over F and let W₁ and W₂ be two subspaces of V. Then,

(9.4.1)

DRAFT

Theorem 9.5.1. Let V be a real vector space. A norm ∥⋅∥ is induced by an inner product if and only if, for all x,y ∈ V, the norm satisfies

DRAFT

(9.5.1)

Definition 9.6.1. [Jordan Curves] A curve in ℂ is a continuous function f : [a,b] → ℂ, where [a,b] ⊆ ℝ.

1.

If the function f is one-one on [a,b) and also on (a,b], then it is called a simple curve.

2.

If f(b) = f(a), then it is called a closed curve.

3.

A closed simple curve is called a Jordan curve.

4.

The derivative (integral) of a curve f = u+iv is defined component wise. If f′ is continuous on [a,b], we say f is a ¹-curve (at end points we consider one sided derivatives and continuity).

5.

A ¹-curve on [a,b] is called a smooth curve, if f′ is never zero on (a,b).

6.

A piecewise smooth curve is called a contour.

7.

A positively oriented simple closed curve is called a simple closed curve such that while traveling on it the interior of the curve always stays to the left. (Camille Jordan has proved that such a curve always divides the plane into two connected regions, one of which is called the bounded region and the other is called the unbounded region. The one which is bounded is considered as the interior of the curve.)

DRAFT Theorem 9.6.2. [Rouche’s Theorem] Let C be a positively oriented simple closed contour. Also, let f and g be two analytic functions on R_C, the union of the interior of C and the curve C itself. Assume also that |f(x)| > |g(x)|, for all x ∈ C. Then, f and f + g have the same number of zeros in the interior of C.

Corollary 9.6.3. [Alen Alexanderian, The University of Texas at Austin, USA.] Let P(t) = tⁿ + a_n-1t^n-1 + + a₀ have distinct roots λ₁,…,λ_m with multiplicities α₁,…,α_m, respectively. Take any ϵ > 0 for which the balls B_ϵ(λ_i) are disjoint. Then, there exists a δ > 0 such that the polynomial q(t) = tⁿ + a_n-1′t^n-1 + + a₀′ has exactly α_i roots (counting with multiplicities) in B_ϵ(λ_i), whenever |a_j - a_j′| < δ.

Corollary 9.6.4. Eigenvalues of a matrix are continuous functions of its entries.

Remark 9.6.5.

1.

[Sign changes in a polynomial] Let P(x) = ∑ ₀ⁿa_ix^n-i be a real polynomial, with a₀≠0. Read the coefficient from the left a₀,a₁,…. We say the sign changes of a_i occur at m₁ < m₂ < < m_k to mean that a_m1 is the first after a₀ with sign opposite to a₀; a_m2 is the first after a_m1 with sign opposite to a_m1; and so on.

2.

[Descartes’ Rule of Signs] Let P(x) = ∑ ₀ⁿa_ix^n-i be a real polynomial. Then, the maximum number of positive roots of P(x) = 0 is the number of changes in sign of the coefficients and that the maximum number of negative roots is the number of sign changes in P(-x) = 0.

Proof. Assume that a₀,a₁,,a_n has k > 0 sign changes. Let b > 0. Then, the coefficients of (x - b)P(x) are

This list has at least k + 1 changes of signs. To see this, assume that a₀ > 0 and a_n≠0. Let the sign changes of a_i occur at m₁ < m₂ < < m_k. Then, setting we see that c_i > 0 when i is even and c_i < 0, when i is odd. That proves the claim.

Now, assume that P(x) = 0 has k positive roots b₁,b₂,,b_k. Then, DRAFT

where Q(x) is a real polynomial. By the previous observation, the coefficients of (x - b_k)Q(x) has at least one change of signs, coefficients of (x-b_k-1)(x-b_k)Q(x) has at least two, and so on. Thus coefficients of P(x) has at least k change of signs. The rest of the proof is similar. _

Lemma 9.7.1. [Rayleigh-Ritz Ratio] Let A ∈ M_n(ℂ) be a Hermitian matrix. Then,

1.

λ₁(A)x^*x ≤ x^*Ax ≤ λ_n(A)x^*x, for each x ∈ ℂⁿ.

2.

λ₁(A) = min_x≠0 = min_∥x∥=1x^*Ax.

3.

λ_n(A) = max_x≠0 = max_∥x∥=1x^*Ax.

Corollary 9.7.2. Let A ∈ M_n(ℂ) be a Hermitian matrix and α = . Then, A has an eigenvalue in the interval (-∞,α] and has an eigenvalue in the interval [α,∞).

Proposition 9.7.3. Let A ∈ M_n(ℂ) be a Hermitian matrix with A = UDU^*, where U is a unitary matrix and D is a diagonal matrix consisting of the eigenvalues λ₁ ≤ λ₂ ≤≤ λ_n. Then, for any positive integer k,1 ≤ k ≤ n,

Theorem 9.7.4. [Courant-Fischer] Let A ∈ M_n(ℂ) be a Hermitian matrix with eigenvalues λ₁ ≤ λ₂ ≤≤ λ_n. Then,

Theorem 9.7.5. [Weyl Interlacing Theorem] Let A,B ∈ M_n(ℂ) be a Hermitian matrices. Then, λ_k(A) + λ₁(B) ≤ λ_k(A + B) ≤ λ_k(A) + λ_n(B). In particular, if B = P^*P, for some matrix P, then λ_k(A + B) ≥ λ_k(A). In particular, for z ∈ ℂⁿ, λ_k(A + zz^*) ≤ λ_k+1(A).

Theorem 9.7.6. [Cauchy Interlacing Theorem] Let A ∈ M_n(ℂ) be a Hermitian matrix. Define  = , for some a ∈ ℝ and y ∈ ℂⁿ. Then,

Corollary 9.7.7. [Inclusion principle] Let A ∈ M_n(ℂ) be a Hermitian matrix and r be a positive integer with 1 ≤ r ≤ n. If B_r×r is a principal submatrix of A then, λ_k(A) ≤ λ_k(B) ≤ λ_k+n-r(A).

DRAFT Theorem 9.7.8. [Poincare Separation Theorem] Let A ∈ M_n(ℂ) be a Hermitian matrix and {u₁,…,u_r}⊆ ℂⁿ be an orthonormal set for some positive integer r,1 ≤ r ≤ n. If further B = [b_ij] is an r × r matrix with b_ij = u_i^*Au_j,1 ≤ i,j ≤ r then, λ_k(A) ≤ λ_k(B) ≤ λ_k+n-r(A).

Corollary 9.7.9. Let A ∈ M_n(ℂ) be a Hermitian matrix and r be a positive integer with 1 ≤ r ≤ n. Then,

Corollary 9.7.10. Let A ∈ M_n(ℂ) be a Hermitian matrix and W be a k-dimensional subspace of ℂⁿ. Suppose, there exists a real number c such that x^*Ax ≥ cx^*x, for each x ∈ W. Then, λ_n-k+1(A) ≥ c. In particular, if x^*Ax > 0, for each nonzero x ∈ W, then λ_n-k+1 > 0. Note that, a k-dimensional subspace need not contain an eigenvector of A. For example, the line y = 2x does not contain an eigenvector of .