Advanced book on Mathematics Olympiad

2.3 Linear Algebra 77

239.Leta 0 = 0 ,a 1 ,...,an,an+ 1 =0 be a sequence of real numbers that satisfy|ak− 1 −
2 ak+ak+ 1 |≤1 fork = 1 , 2 ,...,n−1. Prove that|ak|≤k(n− 2 k+^1 )fork =
1 , 2 ,...,n−1.

240.Prove that the Hilbert matrix
⎛
⎜⎜
⎜
⎝

1 12 13 ···^1 n

1

2

1

3

1

4 ···

1

n+ 1

1

n

1

n+ 1

1

n+ 2 ···

1

2 n− 1

⎞

⎟⎟

⎟

⎠

is invertible. Prove also that the sum of the entries of the inverse matrix isn^2.

2.3.5 Vector Spaces, Linear Combinations of Vectors, Bases.........

In general, a vector spaceVover a field of scalars (which in our book will be onlyC,R,
orQ) is a set endowed with a commutative addition and a scalar multiplication that have
the same properties as those for vectors in Euclidean space.
A linear combination of the vectorsv 1 ,v 2 ,...,vmis a sumc 1 v 1 +c 2 v 2 +···+cmvm
with scalar coefficients. The vectors are called linearly independent if a combination of
these vectors is equal to zero only when all coefficients are zero. Otherwise, the vectors
are called linearly dependent. Ifv 1 ,v 2 ,...,vnare linearly independent and if every
vector inVis a linear combination of these vectors, thenv 1 ,v 2 ,...,vnis called a basis
ofV. The number of elements of a basis of a vector space depends only on the vector
space, and is called the dimension of the vector space. We will be concerned only with
finite-dimensional vector spaces. We also point out that if in a vector space there are
given more vectors than the dimension, then these vectors must be linearly dependent.
The rank of a matrix is the dimension of its row vectors, which is the same as the
dimension of the column vectors. A square matrix is invertible if and only if its rank
equals its size.
Let us see some examples. The first appeared in the Soviet University Student Math-
ematical Competition in 1977.

Example.LetXandB 0 ben×nmatrices,n≥1. DefineBi =Bi− 1 X−XBi− 1 , for
i≥1. Prove that ifX=Bn 2 , thenX=On.

Solution.Because the space ofn×nmatrices isn^2 -dimensional,B 0 ,B 1 ,...,Bn 2 must
be linearly dependent, so there exist scalarsc 0 ,c 1 ,...,cn 2 such that

c 0 B 0 +c 1 B 1 +···+cn 2 Bn 2 =On.

Letkbe the smallest index for whichck =0. Then