58. Rank of Matrix

행렬의 랭크를 쉽게 이해하기 위해서는 벡터의 독립에 대해서 알 필요가 있다.

 

두 벡터 $\vec{u}, \vec{v}$가 다음과 같은 조건을 만족할 경우 서로 독립(Independence)이라고 한다.

$$a\vec{u}+b\vec{v}=\vec{0} \to a=b=0$$

이것을 다르게 해석하면 두 개의 벡터가 독립일 때 그 벡터들을 이용해서 공간 내의 모든 좌표를 나타낼 수 있는 $2$차원 공간이 존재한다는 의미가 된다. 이와 비슷하게 $n$개의 벡터 $\vec{v_1}, \vec{v_2}, \ldots \vec{v_n}$가 다음과 같은 조건을 만족할 경우 서로 독립이라고 한다.

$$a_1\vec{v_1}+a_2\vec{v_2}+\ldots+a_n\vec{v_n}=\vec{0} \to a_1=a_2=\ldots=a_n=0$$

$n$개의 벡터가 서로 독립일 때 이 벡터들의 계수를 적당히 조절하면 $n$차원 공간 내의 모든 좌표를 나타낼 수 있다.

 

다시 행렬로 되돌아와서, $n \times m$ 행렬이 있을 때 이 행렬의 $n$개의 행벡터 중 서로 독립인 벡터를 최대한 많이 고를 수 있다. 또한 이 행렬의 $m$개의 열벡터 중 서로 독립인 벡터를 최대한 많이 고를 수 있다. 이때 두 가지 방법으로 골라낸 벡터의 개수는 항상 서로 같으며, 이 개수가 그 행렬의 랭크(Rank)가 된다.

 

행렬의 랭크를 구할 때는 주로 가우스 소거법을 이용한다. 다음 글에서 자세한 내용을 확인할 수 있다.

 

[연습문제]

 

CF 1101G. (Zero XOR Subset)-less (2300)

$n$개의 수를 모두 XOR한 값이 $0$이라면 답은 $-1$이다. 그렇지 않은 경우 각각의 값을 이진수로 나타낸 다음 이진 행렬을 만든다. 그렇게 만들어진 행렬의 랭크가 답이 된다.