- 행렬의 계수(rank)
행렬을 구성하는 열벡터 간의 독립성, 행벡터 간의 독립성, 또는 행렬에 가우스조던 소거법을 실행했을 때 성공한 피봇(pivot) 연산의 횟수 등 세 가지 방법으로 정의할 수 있다. 물론 이 세 가지 정의는 동일함을 보일 수 있다.
정의 1. 행렬 A에 가우스 조던법을 실행했을 때 성공한 피봇연산의 횟수를 A의 계수 (rank)라고 하고 r(A)라고 표시한다.
정의 2. 행렬 A의 열벡터 중, 서로 독립인 열벡터의 최대 개수를 A의 열계수(column rank)라고 하고 r_c(A)로 표기한다.
정의 3. 행렬 A의 행벡터 중, 서로 독립인 행벡터의 최대 개수를 A의 행계수(row rank)라고 하고 r_r(A)로 표기한다.
* 임의의 행렬에 대해서 위 세 가지의 계수(rank)는 모두 동일하다. 즉, r(A) = r_c(A) = r_r(A) 이다.
정의4. (계수와 빈공간 차원 정리) 행렬 A(m x n 차원) 의 계수와 빈공간 차원의 합은 n이다.또는, A의 행공간 또는 열공간의 차원과 빈공간의 차원을 합하면 n이 된다.
- 기저해와 기저
선형연립방정식 Ax = b (A는 mxn 차원)가 해를 가질 필요충분 조건은 A와 [A|b]의 계수가 같은 것이다. 이때 계수만큼의 변수만을 사용하여 나타낼 수 있는 해가 반드시 존재한다는 것을 알 수 있다. 이러한 해를 기저해라고 한다.
정의5. (기저해) 가우스조던 소거법을 수행한 후, 피봇연산에 성공하지 못한 열의 변수 값을 0으로 놓아 얻어진 해를 기저해(basic solution)라고 한다. 이 때, 0의 값을 지정 받는 변수들을 독립변수, 또는 비기저변수라고 하며, 이에 따라 마지막 우변상수와 같은 값을 갖게 되는 변수들을 종속변수 또는 기저변수라고 한다.
계수 행렬 A의 열 중에서 기저변수에 대응되는 열들만을 기저변수의 순서대로 모아서 만든 부분행렬(submatrix)를 기저해의 기저(basis)라고 부른다.
예시) x1 + x2 + x3 = 1
-x2 + 2x3 = 0
[ 1 1 1 , 0 -1 2 | 1 , 0 ] -> [ 1 0 3 , 0 1 -2 | 1 , 0 ]
피봇연산에 성공하지 못한 A.3의 변수(x3) 값을 0으로 놓아 얻은 해 x^(1) = (1, 0, 0)T 가 기저해가 된다.
이 때 기저는 B^(1) = [A.1, A.2]이다.
[ 1 1 1 , 0 -1 2 | 1 , 0 ] -> [ 2/3 1 0 , 1/3 0 1 | 2/3 , 1/3 ]
피봇연산에 성공하지 못한 A.1의 변수(x1) 값을 0으로 하면
기저해 x^(2) = (0, 2/3, 1/3)T , 기저는 B^(2) = [A.2, A.3]이 된다.
정의 6. 열이 정확히 m-1개가 다른 두 기저해를 서로 이웃하다(adjacent)고 한다.
열벡터가 m-1개 다를 경우, 하나의 공통된 기저해를 가지게 된다.
하나의 기저해는 일반적으로 여러개의 이웃 기저해를 갖는다. 피봇연산의 중심이 되는 원소, 즉 피봇이 어떤 행과 열에 위치하는가에 따라 이웃 기저해가 결정된다. 예를 들어 3에 피봇연산을 하면 x3이 새로운 기저변수로 진입하고, x1이 기저변수에서 탈락할 수 있다. 즉, 피봇이 위치한 행은 탈락하는 기저변수를, 열은 새롭게 진입하는 기저변수를 결정한다.
출처 : 선형계획법(홍성필 저)