Lectia I- Algebra

7/29/2019 Lectia I- Algebra

1/12

13

Lesson I

Determinants, matrices, systems of linear equations

Determinants, minors, Laplace rule, Cramer rule.

The vector space, on the commutative fieldK, designated byMm, n (K) (resp. Mn (K)

in the case m=n) of the matrices of type (m, n) with the elements fromK(in the following,sometimeKmay be only commutative ring with unit).

The multiplication of the matrices, invertible matrices, the rank of a matrix.

Systems of linear equations (Kronecker - Capelli theorem, Rouch theorem).

Systems of homogenous and linear equations.

Completions for matrices

Binet-Cauchy formula. LetA := [aik]from Mm, n (K), B := [bik]from Mn, m (K) andm n. Then

det

...

...

...

......

AB

a a

a a

b b

b b

= < <

1 1

1

1

1

1

1

1

1k k

mk mk

k k n

k k m

k k m

m

m

m

1

m m

M M M M .

To shorten the writing one uses the notation:

Mi ij j

1

1

...

...p

p

designates the minor of the matrixMformed with the lines i1 , . . . , ip and the

columns j1 , . . . ,jp .

C: =AB =

a b a b

a b a b

1 11

11

11 1

1 1

1

1 1

1

r rr

n

r r mr

n

m r rr

n

m r r mr

n

m m

m

m m

m

= =

= =

. . .

. . .

M M . Followings the columns of det Cone can write

detC= . . .

. . .

. . .r

n r r r r m

m r r m r r m

r

n

1

m m

m m

m= =

1

1 1 1

1

1

1 1

1 1

a b a b

a b a b

M M and also, observing the common factor at each

column, detC= . . .

. . .

. . .. . .

r

n

mr

n

r r mm

m

1

11 11

1

1

= =

A

m

r rb b . In the sum there are n m terms and

those, to which in the sequence r1 , . . . , rm two or more terms are equal, are equal to 0, so

detCis the sum ofA nm terms A

m

r rb b

1

111

. . .

. . .. . .

mr r mm

at which r1 , . . . , rm are different

two by two. One distributes them in Cn

mgroups, taking in a group those which differ only

by the succession of the indices r1 , . . . , rm , consequently detC = Tk , .. ., k 1 k k n

1 m

1 m < <

.. .

,


2/12

14

Tk1, . . . , km: = mi1im1

m1...

...

...1bb

iimA

, where is the permutation k k

i i

1

1

. . .

. . .

m

m

. But

A1

1

. . .

. . .

m

i im

= ()A

1

1

. . .

. . .

m

k km

, () the signature of : =

k k

i i

1

1

. . .

. . .

m

m

(= (1)

,

the number of inversions presented by , t the number of transpositions in which this is

decomposed), hence Tk1, . . . , km= A

mi1i

m1m1

)(...

...1bb

kk

mK . On the other hand,

k k

i i

1

1

. . .

. . .

m

m

bi11 . . . bim m =

1

11 1

. . .

. . .. . .

m

j jb b

m

k j k jm m

, so Tk1, . . . , km= A

m1 ...

...1

kk

m

m mm11Sjkjk ...)( bb = A

1

1

. . .

. . .

m

k km

B k km

1

1. . .. . .

m , whence the conclusion.

Example. A =t

0123

2101,

1023

2101

=

B , detAB = ? The terms of the sum are given by the

couples (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), detAB = ++

11

310311

2031

2301

02

10

02

31

13

21

+

+

11

20

0 2

2 1

0 2

2 0

1 2

0 1

1 1

2 0

+

= 30.

Corollary. A, B Mn (K) det AB = det A det B.A

t. Let A : = [aik] be from Mn (K). A

t: = [bik], where bik= aki , i, k= 1,n (the

transpose matrix ofA; whenA =At ,A is namedsymmetrical).A. LetA : = [aik] be a matrix fromMn (K). One notesA: = [bik], where bik=Aki , i, k

= 1,n , Aki the cofactor of the element aki . We have AA= A

A = = (detA)E, E the unit

matrix, therefore whenA is nonsingular, A1 =1

detAA

.

Complex matrix (real matrix). All the elements of this are complex numbers (realnumbers).

Triangular matrix. The matrix A : = [aik] from Mn (K) is by definition uppertriangular (resp. lower triangular) when i > k aik= 0 (resp. i < kaik= 0 ). IfA isupper and lower triangular, it is named diagonal matrix and is designated bydiag { a11 , a22 , . . . , ann }.

Nilpotent matrix.A fromMn (K) is called nilpotentif p in N so thatAp = 0.

f(A). LetA be matrix fromMn (K) andfa polynomial fromK[X], f(X) = a Xkp k

p

=0 .By definition f(A) = a0A

p + a1Ap1 + . . . + ap1A + apE, E the unit matrix. If f=g + h

resp. f=gh, gand h fromK[X], then f(A) =g(A) + h (A) resp.f(A) =g(A) h (A).

Identifications. xi , i = 1,n being elements from K, one pass without warning andwithout change the notation from the vectorx := (x1 , . . . , xn ) in K

n to the row matrix

x = [x1 xn ], or to the column matrixx = [x1 xn ]t, or to the row or column of a matrix

with the elements in the sequence x1 , ,xn .Partition in blocks. Let A : = [aik] be a matrix from Mm,n (K). Fix the following

packagesL1 ,L2 , . . . ,Lp of consecutive rows:L1 with the first i1 rows,L2 with the next i2


3/12

15

rows, L3 with the next i3 lines, . . . , Lp with the last ip lines. Remark that i1 + i2 + . . .+ ip = m. Fix also the next packages C1 , C2 , . . . , Cq of consecutive columns: C1 with thefirst k1 columns, C2 with the next k2 columns, . . . , Cq with the last kq columns. Oneobserves that k1 + k2 + . . . + kq = n. The rows fromL1 and the columns from C1 determinethe sub-matrix A11 , the rows from L1 and the columns from C2 establish the sub-matrixA12 , . . . , the rows fromL1 and the columns from Cq establish the sub-matrixA1q . PassingtoL2 one obtains in the same manner the sub-matrices A21 , . . . , A2q , . . . , passing to Lpone obtains the sub-matrices Ap1 , . . . , Apq . Auv , u = 1,p , v = 1,q are named blocks, they

achieve by definition a partition ofA. For instance,

0420

0412= [A11A12], where A11 =

420

412,A12 =

0

0.

The matrix A from Mn (K) is by definition quasi-diagonal if it admits a partition in

blocksAuv , u, v = 1,m , m 2 e.g. u vAuv = 0 and the matricesAuu , u = 1,m are square.

In this case one use the notationA = diag {A11 , . . . ,Amm}. We have detA = detAiii=1

m

.The multiplication rule can be generalized at the matrices partitioned in blocks.

1.1 Theorem. LetA : = [a ik] be from Mm,l(K) with the blocks A uv of type (mu , lv ),

u = 1,p , v = 1, q andB : = [b ik]from Ml,n (K) with the blocks B vw of type (lv , nw ), v = 1, q ,

w = 1,r. Then the product matrix AB is partitioned in the blocks Cuw : =

A B u = 1,puv vw

v=1

q

, , w = 1,r .

Cuw is of type (mu , nw ) because each term has this type. Consider the matrix C: =

C C

C C

11 1

1

. . .

. . .

r

p p r

M M

, correctly as Cu1 , Cu2 , . . . , Cu r have mu rows and C1w , C2w , . . . , Cpw

have nw columns. It follows to show that C=AB, i. e., if C: = [cij ], then cij = a bl

is sjs=

1

,

i = 1,m ,j = 1,n . Indeed, let cij be in the position (k, t) of the blockCuw , then cij is the sum

of the elements in the position (k, t) in the matricesAuvBvw , v = 1,q . But the element in theposition (k, t) of the matrix AuvBvw is the sum of the products of the lv elements from therow kofAuv with the elements of the tcolumn ofBvw . But the elements of the krow from

Auv are identical with certain elements of the i row fromA and namely with the elements ais

wheres varies in accordance with the inequalities:sl1 ifu = 1; l s lk=1

u

k=1

u

< 1

ifu > 1.

Reasoning likewise about the elements of the t column from Bvw one obtains

cij = a b a b a bl

l

l l

l l

l

is sjs

is sjs

is sjs q= = +

+

= +

+ + +1 1 1

1

1

1 2

. . . = a bl

is sjs=

1

(l1 + l2 + . . . + lq = ll1 + + . . . + lq1 =

llq ). Example.A = diag {A1 , . . .,Am } Ak= diag {A1k, . . . ,Amk} kdin N.


4/12

16

The reduction method. It gives an excellent algorithm to calculate the inverse of amatrix, algorithm which is blocked when this has not an inverse. The method is based on

the remark

If C[AE] = [EB] , A, B, Cfrom Mn (K), E the unit matrix, then B = C = A1.

[EB] = C[AE] = [CA CE] = [CA C] and so the conclusion. Consider the matrix of the type (n, 2n)

U: = [AE] =

a a aa a a

a a a

11 12 1

21 22 2

1 2

1 0 00 1 0

0 0 1

. . . . . .

. . . . . .

. . . . . .

n

n

n n nn

M M M M M M

(the vertical line helps in the development of the algorithm, at the end of this on the right

there is the chosen matrixA1 ). One makes elementary transformations about the matrix U

only on therows of this (multiplication of a row with 0 fromK, addition to a row ofanother row multiplied with from K, change between them of two rows; each of thereverts to the multiplication of U to the left with an invertible matrix of type (n, n), see4.37 , 4.38 , 4.39 ) until one arrives to a matrix of the form [EB] : Tp Tp1 . . .T2 T1 [AE] = [EB]. According to the last affirmation, B =A

1 . Here is the unfolding of the

calculus. Suppose a11 0, put it in a border and it becomes pivot(ifa11 = 0 and even thefirst column is 0, the algorithm is blocked,A is not invertible; if al1 0, one interchangesthe row 1 with row l). The following matrix of the algorithm is U1 : = [bik] of type (n, 2n)where the first row is the pivot row divided by the pivot and the others are obtained from

the row of the pivot with the rectangle rule , namely

row 2: b21 = 0, b22 = a22 a12 , b23 = a23 a13 etc. , where =a

a

21

11

row 3: b31 = 0, b32 = a32 a12 , b33 = a33 a13 etc. , = aa31

11

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

row n: bn1 = 0, bn2 = an2 a12 , bn3 = an3 a13 etc. , =aa

n1

11

(on each row is constant; visualize the rule !). So the first column from U1 has theelements 1, 0, . . . , 0. The algorithm continues. If bj2 = 0, 2 jn blockade, A is notinvertible, and ifbl2 0, 2 < ln, one changes the row 2 with the row land so one canassume b22 0. One put this in a square getting a pivot and pass to the following matrixU2 : = [cik] which has the rowsrow 2: the line of the pivot divided to this

row 1: c11 = 1, c12 = 0, c13 = b13 b23 , c14 = b14 b24 etc. , =b

b

12

22

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

row n: cn1 = 0, cn2 = 0, cn3 = bn3 b23 , cn4 = bn4 b24 etc. , =bb

n2

22

(remark that until in the column which corresponds to the pivot the rows does not suffer

any change and above and below the element 1 is 0) and so on. IfA is invertible,Un = [E A

1].


5/12

17

Example.A =

2 1 0 03 2 0 0

1 1 3 4

2 1 2 3

A

1 = ?

U=

2 1 0 0 1 0 0 0

3 2 0 0 0 1 0 0

1 1 3 4 0 0 1 0

2 1 2 3 0 0 0 1

, U1 =

11

20 0

1

20 0 0

01

20 0

3

21 0 0

01

23 4

1

20 1 0

0 2 2 3 1 0 0 1

, U2 =

1 0 0 0 2 1 0 0

0 1 0 0 3 2 0 0

0 0 3 4 1 1 1 0

0 0 2 3 7 4 0 1

,

U3 =

1 0 0 0 2 1 0 0

0 1 0 0 3 2 0 0

0 0 14

3

1

3

1

3

1

30

0 0 01

3

23

3

14

3

2

31

, U4 =

1 0 0 0 2 1 0 0

0 1 0 0 3 2 0 00 0 1 0 31 19 3 4

0 0 0 1 23 14 2 3

. A

1 is in the right of the vertical

line.

Completions for systems of linear equations

Consider the system ofm linear equations with n unknowns (1) a xis s

s=1

n

= bi , i = 1,m ,

aij , bi K, K commutative field. IfA: = [aij ], B: = [b1 . . . bn ]t and adopt the matrix

notationx : = [x1 . . .xn ]t

for the unknowns, then (1) may be transcribed in a matrix form

Ax = b. The set of the solutions of the linear and homogeneous system Ax = 0 is a vectorsubspace ofKn , one notes this KerA, the nucleus ofA.

1.2 dim Ker A = n rk A.

The proof takes into account the solution of the homogeneous linear system. Note

r: = rkA. One can admit the partition A =A A

A A11 12

21 22

with detA11 as principal minor and

one considers ej vector fromKnr which in the position j has 1 and in the others 0, j vector

fromKn equal to

A A e

e1 1

1

12 j

j

,j = 1,n r and letEbe the vector subspace ofKn generated

by 1 , . . . , nr. These being linearly independent, dimE= n r and we prove that

E= KerA. E Ker A. A j =

+=

j22j211

1112

1.2

j

j211

11

2212

2111 0

eAeAAAe

eAAAA

AA=

0

0= 0,

because A11x'+A12 ej = 0 A21x'+ A22 ej = 0 and as x'= A111

A12 ej , it results

A21A111

A12 ej + +A22 ej = 0. Ker A E. Indeed, if (2) Ax = 0, let be xt= [x1

tx2t] with

x2 Knr, hencex2 =

=

rn

1jjje , j Kand asx1 =

( )2

11

1

12 2A A x , we havex =

=

rn

1jjj .

Gauss method. Consider the system ofn linear equations with n unknowns


6/12

18

(3)

a x a x a x aa x a x a x a

a x a x a x a

11 1 1 2 2 1 1 1

2 1 1 2 2 2 2 2 1

1 1 2 2 1

+ + + =+ + + =

+ + + =

+

+

+

. . .. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .

n n n

n n n

n n n n n n n

, aikK,Kcommutative field.

Ifa11 0 (principal coefficient), dividing in the first equation from (3) with a11 , (4) x1 +

+ b2x2 + . . . + bnxn = bn+1 . One multiplies in (4) successively by a21 , a31 , . . . , an1and add respectively the second, the third, . . . , the n-th equation from (3), it results

(5)

a x a x a x a

a x a x a x a

a x a x a x a

22

1

2 23

1

3 2 2 1

1

32

1

2 33

1

3 3 3 1

1

2

1

2 3

1

3 1

1

+ + + =

+ + + =

+ + + =

+

+

+

. . .

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .

n

1

n n

n

1

n n

n n n n

1

n n n

.

In (5) the unknown x1 was eliminated and (4) + (5) is equivalent with (3). If a221

0

(principal coefficient) one repeats the procedure to eliminate the unknownx2 , one obtains(6)x2 + b x b x2

1

3

1+ +. . .n n

= bn+11

,

(7)

a x a x a x a

a x a x a x a

a x a x a x a

33

2

3 34

2

4 3 3 1

2

43

2

3 44

2

4 4 4 1

2

3

2

3 4

2

4 1

2

+ + + =

+ + + =

+ + + =

+

+

+

. . .

. . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .

n

2

n n

n

2

n n

n n n n

2

n n n

and (4) + (6) + (7) is equivalent with (3) etc. , and in the hypothesis that all the principal

coefficients are 0, one obtains the system, equivalent to (3),

(8)

x b x b x b

x b x b x b

x b x b

x b ba

a

1 2 2 1

2 31

31

11

1

2

1

2

1

1

1

1 1

1

1

+ + + =

+ + + =

+ =

= =

+

+

+

+

+ +

. . .

. . .

, : .

n n n

n n n

n n

n

n n

n

n n

n

n

n n n

n

n n

n

. . . . . . . . . . . . . . . . . .

(8) is solved bottom up.

Let B the matrix of the unknown coefficients from (8). Taking into account the

operations effectuated, we have 1 = detB =det

. . .

A

a a a a11 22

1

33

2 1

n n

n , consequently the Gauss

method can be used in the calculus of the determinants. It can be also used for invert

matrix. Indeed, ifA := [aik],A1 := [xik] thenAA1 =E a xis sk s=1

n

= ik, i, k= 1,n , i.e. nsystems of linear equations with n2 unknowns, but to which the Gauss method can beapplied simultaneous, all the systems having the same matrixA.

The square root method. Consider the system of linear equation in matrix writing (9)Ax = b, AMn (C) symmetrical, bC

n . Put A in the form A = Tt T with T= [tij ] upper

triangular. The elements tij are clearly obtained from t11 = a ta

t11 11

11

;j

j= , j =


7/12

19

= 2 212

1

1

1

1

, ; , , ;n t a t i n t t

a t tii ii si

s

i

ij

ii

ij si sjs

i

= = =

=

=

, 1 i


8/12

20

exists, as detA 0). Obviously~ ~

A At = . Let be (15) C= [cik] : =T. Taking into account(14), from (15) one obtains ci1 = ai1 , i = 1 1,n +

(16) 1 < ln + 1 :c a t a l i n

c i l

l l

l

l

l

i ir r r

i

i

= + +

=

Lectia I- Algebra

Documents

Transcript of Lectia I- Algebra