【선형대수학】 프로베니우스 rank 부등식 (Frobenius' Inequality)

프로베니우스 rank 부등식 (Frobenius' Inequality)

 

추천글 : 【선형대수학】 선형대수학 목차

---

1. 명제 [본문]

2. 증명 [본문]

---

 

1. 명제 [목차]

A ∈ M k×l(ℂ), B ∈ M l×m(ℂ), C ∈ M m×n(ℂ)인 임의의 세 행렬 A, B, C에 대해 다음 부등식이 성립한다.

rank (AB) + rank (BC) ≤  rank (B) + rank (ABC) 가 성립한다.

 

 

2. 증명 [목차]

⑴ 부호 약속 : 주어진 행렬에 대해 

rank (·) : rank

ker (·) : null space (= kernel)

ker (T) = {x | Tx = O}

im (·) : column space (= image)

T : V → W, im (T) = {Tv | v ∈ V}

 

⑵ lemma 1. rank (AB) = rank (B)－ dim(im(B) ∩ ker (A))

T : C(B) → C(AB), 즉 T(y) = Ay, ∀y ∈ C(B)인 사상을 생각하자.

이때 임의의 c ∈ ℝ와 y1, y2 ∈ C(B)에 대하여, y1 = Bx1, y2 = Bx2인 x1, x2를 찾을 수 있으므로

T(cy1 + y2) = T(B(cx1 + x2)) = AB(cx1 + x2) = cABx1 + ABx2 = cT(y1) + T(y2)이다.

따라서 사상 T는 선형사상이다.

 

또한 ker (T) = {y ∈ C(B) | Ay = O} = {y | Ay = O and y ∈ C(B)}이므로 

 ker (T) = Nullity (A) ∩ C(B)가 성립한다.

 

따라서 Rank－Nullity Theorem을 적용하면,

dim(C(B)) = dim(im(B)) = rank (B) 

dim(C(B)) = dim(im(T)) + dim(ker (T)) = dim(AB) + dim(Nullity (A) ∩ C(B)) 

dim(C(B)) = rank (AB) + dim(Nullity (A) ∩ C(B))

 

⑶ lemma 2. im(BC) ∩ ker (A) ⊆ im(B) ∩ ker (A)

 

B : ℝm → ℝl, C : ℝn → ℝm에 대하여,

im(B) = {Bx | x ∈ ℝm}이므로, ℝl으로 옮기는 B의 정의역은 ℝm이다.

그런데 im(BC) = {Bx | x ∈ C(C)}, C(C) = {Cy | y ∈ ℝn}이므로 ℝl으로 B의 정의역이 C(C)이다. 

C(C) ⊆ ℝm이므로 im(BC) ⊆ im(B)이다.

따라서 명백하게 lemma 2.가 성립한다.

 

⑷ lemma 3. rank (BC) = rank (ABC) + dim(im(BC) ∩ ker (A))

lemma 1.에서 A= A, B=BC를 대입하면,

rank (ABC) = rank (BC)－ dim(im(BC) ∩ ker (A))

⇔ rank (BC) = rank (ABC) + dim(im(BC) ∩ ker (A))

 

이제 lemma 1.과 lemma 3.으로부터 다음 식을 얻는다. 

rank (AB) + rank (BC) = rank (B) + rank (ABC) + dim(im(BC) ∩ ker (A))－ dim(im(B) ∩ ker (A)) 

                                              ≤ rank (B) + rank (ABC)

(∵ dim(im(BC) ∩ ker (A))－ dim(im(B) ∩ ker (A)) ≤ 0  due to lemma 2.)

따라서 준 명제를 증명하였다.

 

⑸ 레퍼런스 : https://math.stackexchange.com/questions/497830/frobenius-inequality-rank

Frobenius Inequality Rank

 

입력: 2015.08.27 11:14