Advanced book on Mathematics Olympiad

Algebra 435

rank

⎛

⎜

⎜⎜

⎝

23 ···n+ 1

34 ···n+ 2

..

.

..

.

... ..

.

n+ 1 n+ 2 ··· 2 n

⎞

⎟

⎟⎟

⎠

=rank

⎛

⎜

⎜⎜

⎝

23 ···n+ 1

11 ··· 1

..

.

..

.

... ..

.

11 ··· 1

⎞

⎟

⎟⎟

⎠

=rank

⎛

⎜

⎜⎜

⎜⎜

⎝

12 ···n

11 ··· 1

00 ··· 0

..

.

..

.

... ..

.

00 ··· 0

⎞

⎟

⎟⎟

⎟⎟

⎠

= 2.

(12th International Competition in Mathematics for University Students, 2005)

244.ThepolynomialsPj(x)=(x+j)k,j= 0 , 1 ,...,n−1, lie in the(k+ 1 )-dimensional
real vector space of polynomials of degree at mostk. Becausek+ 1 <n, they are linearly
dependent. The columns consist of the evaluations of these polynomials at 1, 2 ,...,n,
so the columns are linearly dependent. It follows that the determinant is zero.

245.We prove this property by induction onn. Forn=1, iff 1 is identically equal to
zero, then so isf. Otherwise, pick a vectore/∈f 1 −^1 ( 0 ). Note that any other vector
v∈Vis of the formαe+wwithα∈Randw∈f 1 −^1 ( 0 ). It follows thatf =ff(e) 1 (e)f 1 ,
and the base case is proved.
We now assume that the statement is true forn=k−1 and prove it forn=k.By
passing to a subset, we may assume thatf 1 ,f 2 ,...,fkare linearly independent. Because
fkis linearly independent off 1 ,f 2 ,...,fk− 1 , by the induction hypothesis there exists a
vectoreksuch thatf 1 (ek)=f 2 (ek)= ··· =fk− 1 (ek)=0, andfk(ek) =0. Multiplying
ekby a constant, we may assume thatfk(ek)=1. The vectorse 1 ,e 2 ,...,ek− 1 are defined
similarly, so thatfj(ei)=1ifi=jand 0 otherwise.
For an arbitrary vectorv∈Vand fori= 1 , 2 ,...,k, we have

fi

⎛

⎝v−

∑k

j= 1

fj(v)ej

⎞

⎠=fi(v)−

∑k

j= 1

fj(v)fi(ej)=fi(v)−fi(v)fi(ei)= 0.

By hypothesisf(v−

∑k

j= 1 fj(v)ej)=0. Sincefis linear, this implies

f(v)=f(e 1 )f 1 (v)+f(e 2 )f 2 (v)+···+f(ek)fk(v), for allv∈V.

This expressesfas a linear combination off 1 ,f 2 ,...,fk, and we are done.
(5th International Competition in Mathematics for University Students, 1998)

246.First solution: We will prove this property by induction onn. Forn=1itis
obviously true. Assume that it is true forn−1, and let us prove it forn. Using the induction
hypothesis, we can findx 1 ,x 2 ,...,xn− 1 ∈Ssuch thata 1 x 1 +a 2 x 2 + ··· +an− 1 xn− 1