## Tuesday, November 7, 2006

### Rank Me! Topic: Linear Algebra.

Problem: (2005 IMC Day 1 - #1) Let $A$ be a matrix such that $A_{ij} = i+j$. Find the rank of $A$.

Solution: Well we clearly have the $k$th row of the matrix equal to

$R_k = (k+1, k+2, \ldots, k+n)$.

So we just need to reduce this to row-echelon form through elementary operations. Well, we can take

$R_k \rightarrow R_k-R_{k-1}$

for $k \ge 2$, so we now have

$R_1 = (2, 3, \ldots, n+1)$ and $R_k = (1, 1, \ldots 1)$

for $k \ge 2$. Now for all $k > 2$, take

$R_k \rightarrow R_k-R_2$

and take $R_1 \rightarrow R_1-2R_2$ so our matrix becomes

$R_1 = (0, 1, \ldots, n-1)$, $R_2 = (1, 1, \ldots, 1)$, and $R_k = (0, 0, \ldots, 0)$

for $k>2$. Swapping $R_1$ and $R_2$ gives us row-echelon form, from which we can easily see that there are two pivot elements, which means the rank of $A$ is two. Note that for $k = 1$ the rank is one. QED.

--------------------

Comment: Really not a difficult problem if you know any fundamental linear algebra and the operations you can perform on a matrix to calculate its rank. Linear algebra is super cool and even useful on competitions (when you get to college)!

--------------------

Practice Problem: For any matrix $A$, prove that $\text{rank}(A) = \text{rank}(A^T)$.