**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) $.

## No comments:

## Post a Comment