Section 8

Systems of linear equations

[26/81%]
Show
LaTeX
Problem 8.1

Find the general solution and one particular solution of the system of linear equations, using the Gauss method:

?
(a)

{5x1+3x2+5x3+12x4=10,2x1+2x2+3x3+5x4=4,x1+7x2+9x3+4x4=2;\begin{cases} 5 x_{1}+3 x_{2}+5 x_{3}+12 x_{4}=10, \\ 2 x_{1}+2 x_{2}+3 x_{3}+5 x_{4}=4, \\ x_{1}+7 x_{2}+9 x_{3}+4 x_{4}=2 ; \end{cases}

(b)

{−9x1+6x2+7x3+10x4=3,−6x1+4x2+2x3+3x4=2,−3x1+2x2−11x3−15x4=1;\begin{cases} -9 x_{1}+6 x_{2}+7 x_{3}+10 x_{4}=3, \\ -6 x_{1}+4 x_{2}+2 x_{3}+3 x_{4}=2, \\ -3 x_{1}+2 x_{2}-11 x_{3}-15 x_{4}=1 ; \end{cases}

(c)

{−9x1+10x2+3x3+7x4=7,−4x1+7x2+x3+3x4=5,7x1+5x2−4x3−6x4=3;\begin{cases} -9 x_{1}+10 x_{2}+3 x_{3}+7 x_{4}=7, \\ -4 x_{1}+7 x_{2}+x_{3}+3 x_{4}=5, \\ 7 x_{1}+5 x_{2}-4 x_{3}-6 x_{4}=3 ; \end{cases}

(d)

{12x1+9x2+3x3+10x4=13,4x1+3x2+x3+2x4=3,8x1+6x2+2x3+5x4=7;\begin{cases} 12 x_{1}+9 x_{2}+3 x_{3}+10 x_{4}=13, \\ 4 x_{1}+3 x_{2}+x_{3}+2 x_{4}=3, \\ 8 x_{1}+6 x_{2}+2 x_{3}+5 x_{4}=7 ; \end{cases}

(e)

{−6x1+9x2+3x3+2x4=4,−2x1+3x2+5x3+4x4=2,−4x1+6x2+4x3+3x4=3;\begin{cases} -6 x_{1}+9 x_{2}+3 x_{3}+2 x_{4}=4, \\ -2 x_{1}+3 x_{2}+5 x_{3}+4 x_{4}=2, \\ -4 x_{1}+6 x_{2}+4 x_{3}+3 x_{4}=3 ; \end{cases}

(f)

{8x1+6x2+5x3+2x4=21,3x1+3x2+2x3+x4=10,4x1+2x2+3x3+x4=8,3x1+3x2+x3+x4=15,7x1+4x2+5x3+2x4=18;\begin{cases} 8 x_{1}+6 x_{2}+5 x_{3}+2 x_{4}=21, \\ 3 x_{1}+3 x_{2}+2 x_{3}+x_{4}=10, \\ 4 x_{1}+2 x_{2}+3 x_{3}+x_{4}=8, \\ 3 x_{1}+3 x_{2}+x_{3}+x_{4}=15, \\ 7 x_{1}+4 x_{2}+5 x_{3}+2 x_{4}=18 ; \end{cases}

(g)

{2x1+5x2−8x3=8,4x1+3x2−9x3=9,2x1+3x2−5x3=7,x1+8x2−7x3=12;\begin{cases} 2 x_{1}+5 x_{2}-8 x_{3}=8, \\ 4 x_{1}+3 x_{2}-9 x_{3}=9, \\ 2 x_{1}+3 x_{2}-5 x_{3}=7, \\ x_{1}+8 x_{2}-7 x_{3}=12 ; \end{cases}

(h)

{6x1+4x2+5x3+2x4+3x5=1,3x1+2x2−2x3+x4=−7,9x1+6x2+x3+3x4+2x5=2,3x1+2x2+4x3+x4+2x5=3.\begin{cases} 6 x_{1}+4 x_{2}+5 x_{3}+2 x_{4}+3 x_{5}=1, \\ 3 x_{1}+2 x_{2}-2 x_{3}+x_{4}=-7, \\ 9 x_{1}+6 x_{2}+x_{3}+3 x_{4}+2 x_{5}=2, \\ 3 x_{1}+2 x_{2}+4 x_{3}+x_{4}+2 x_{5}=3. \end{cases}

Problem 8.2

Investigate the system and find the general solution depending on the value of the parameter λ\lambda:

?
(a)

{18x1+6x2+3x3+2x4=5,−12x1−3x2−3x3+3x4=−6,4x1+5x2+2x3+3x4=3,λx1+4x2+x3+4x4=2;\begin{cases} 18 x_{1}+6 x_{2}+3 x_{3}+2 x_{4}=5, \\ -12 x_{1}-3 x_{2}-3 x_{3}+3 x_{4}=-6, \\ 4 x_{1}+5 x_{2}+2 x_{3}+3 x_{4}=3, \\ \lambda x_{1}+4 x_{2}+x_{3}+4 x_{4}=2 ; \end{cases}

(b)

{−6x1+8x2−5x3−x4=9,−2x1+4x2+7x3+3x4=1,−3x1+5x2+4x3+2x4=3,−3x1+7x2+17x3+7x4=λ;\begin{cases} -6 x_{1}+8 x_{2}-5 x_{3}-x_{4}=9, \\ -2 x_{1}+4 x_{2}+7 x_{3}+3 x_{4}=1, \\ -3 x_{1}+5 x_{2}+4 x_{3}+2 x_{4}=3, \\ -3 x_{1}+7 x_{2}+17 x_{3}+7 x_{4}=\lambda ; \end{cases}

(c)

{2x1+5x2+x3+3x4=2,4x1+6x2+3x3+5x4=4,4x1+14x2+x3+7x4=4,2x1−3x2+3x3+λx4=7;\begin{cases} 2 x_{1}+5 x_{2}+x_{3}+3 x_{4}=2, \\ 4 x_{1}+6 x_{2}+3 x_{3}+5 x_{4}=4, \\ 4 x_{1}+14 x_{2}+x_{3}+7 x_{4}=4, \\ 2 x_{1}-3 x_{2}+3 x_{3}+\lambda x_{4}=7 ; \end{cases}

(d)

{2x1−x2+3x3+4x4=5,4x1−2x2+5x3+6x4=7,6x1−3x2+7x3+8x4=9,λx1−4x2+9x3+10x4=11;\begin{cases} 2 x_{1}-x_{2}+3 x_{3}+4 x_{4}=5, \\ 4 x_{1}-2 x_{2}+5 x_{3}+6 x_{4}=7, \\ 6 x_{1}-3 x_{2}+7 x_{3}+8 x_{4}=9, \\ \lambda x_{1}-4 x_{2}+9 x_{3}+10 x_{4}=11 ; \end{cases}

(e)

{2x1+3x2+x3+2x4=3,4x1+6x2+3x3+4x4=5,6x1+9x2+5x3+6x4=7,8x1+12x2+7x3+λx4=9;\begin{cases} 2 x_{1}+3 x_{2}+x_{3}+2 x_{4}=3, \\ 4 x_{1}+6 x_{2}+3 x_{3}+4 x_{4}=5, \\ 6 x_{1}+9 x_{2}+5 x_{3}+6 x_{4}=7, \\ 8 x_{1}+12 x_{2}+7 x_{3}+\lambda x_{4}=9 ; \end{cases}

(f)

{λx1+x2+x3=1,x1+λx2+x3=1,x1+x2+λx3=1;\begin{cases} \lambda x_{1}+x_{2}+x_{3}=1, \\ x_{1}+\lambda x_{2}+x_{3}=1, \\ x_{1}+x_{2}+\lambda x_{3}=1 ; \end{cases}

(g)

{λx1+x2+x3+x4=1,x1+λx2+x3+x4=1,x1+x2+λx3+x4=1,x1+x2+x3+λx4=1;\begin{cases} \lambda x_{1}+x_{2}+x_{3}+x_{4}=1, \\ x_{1}+\lambda x_{2}+x_{3}+x_{4}=1, \\ x_{1}+x_{2}+\lambda x_{3}+x_{4}=1, \\ x_{1}+x_{2}+x_{3}+\lambda x_{4}=1 ; \end{cases}

(h)

{(1+λ)x1+x2+x3=1,x1+(1+λ)x2+x3=λ,x1+x2+(1+λ)x3=λ2;\begin{cases} (1+\lambda ) x_{1}+x_{2}+x_{3}=1, \\ x_{1}+(1+\lambda ) x_{2}+x_{3}=\lambda , \\ x_{1}+x_{2}+(1+\lambda ) x_{3}=\lambda^{2} ; \end{cases}

(i)

{(1+λ)x1+x2+x3=λ2+3λ,x1+(1+λ)x2+x3=λ3+3λ2,x1+x2+(1+λ)x3=λ4+3λ3.\begin{cases} (1+\lambda ) x_{1}+x_{2}+x_{3}=\lambda^{2}+3 \lambda , \\ x_{1}+(1+\lambda ) x_{2}+x_{3}=\lambda^{3}+3 \lambda^{2}, \\ x_{1}+x_{2}+(1+\lambda ) x_{3}=\lambda^{4}+3 \lambda^{3}. \end{cases}

Problem 8.3

Find all vectors of the space Rn\mathbb {R}^{n} that map to the vector b∈Rmb \in \mathbb {R}^{m} under the linear mapping Rn→Rm\mathbb {R}^{n} \rightarrow \mathbb {R}^{m} given by the matrix AA:

?
(a)

A=(32−534−952−881−7),b=(79812)A=\left(\begin{array}{ccc}3 & 2 & -5 \\ 3 & 4 & -9 \\ 5 & 2 & -8 \\ 8 & 1 & -7\end{array}\right), \quad b=\left(\begin{array}{c}7 \\ 9 \\ 8 \\ 12\end{array}\right);

(b)

A=(1−3−3−142−6−3−13−9−5−6),b=(8−5−4)A=\left(\begin{array}{rrrr}1 & -3 & -3 & -14 \\ 2 & -6 & -3 & -1 \\ 3 & -9 & -5 & -6\end{array}\right), \quad b=\left(\begin{array}{r}8 \\ -5 \\ -4\end{array}\right);

(c)

A=(1−2−1−2−33−6−2−4−53−6−4−8−132−4−1−1−2),b=(−2−3−9−1)A=\left(\begin{array}{ccccc}1 & -2 & -1 & -2 & -3 \\ 3 & -6 & -2 & -4 & -5 \\ 3 & -6 & -4 & -8 & -13 \\ 2 & -4 & -1 & -1 & -2\end{array}\right), \quad b=\left(\begin{array}{c}-2 \\ -3 \\ -9 \\ -1\end{array}\right);

(d)

A=(194−532252322176−12234),b=(13275)A=\left(\begin{array}{rrrr}1 & 9 & 4 & -5 \\ 3 & 2 & 2 & 5 \\ 2 & 3 & 2 & 2 \\ 1 & 7 & 6 & -1 \\ 2 & 2 & 3 & 4\end{array}\right), \quad b=\left(\begin{array}{c}1 \\ 3 \\ 2 \\ 7 \\ 5\end{array}\right);

(e)

A=(113−23224−13335−23228−39),b=(1212)A=\left(\begin{array}{rrrrr}1 & 1 & 3 & -2 & 3 \\ 2 & 2 & 4 & -1 & 3 \\ 3 & 3 & 5 & -2 & 3 \\ 2 & 2 & 8 & -3 & 9\end{array}\right), \quad b=\left(\begin{array}{c}1 \\ 2 \\ 1 \\ 2\end{array}\right);

(f)

A=(3−6−141−2−372−4−1431),b=(−7−5−10)A=\left(\begin{array}{cccc}3 & -6 & -1 & 4 \\ 1 & -2 & -3 & 7 \\ 2 & -4 & -14 & 31\end{array}\right), \quad b=\left(\begin{array}{c}-7 \\ -5 \\ -10\end{array}\right);

(g)

A=(213−21635−43217−41422−33),b=(45116)A=\left(\begin{array}{ccccc}2 & 1 & 3 & -2 & 1 \\ 6 & 3 & 5 & -4 & 3 \\ 2 & 1 & 7 & -4 & 1 \\ 4 & 2 & 2 & -3 & 3\end{array}\right), \quad b=\left(\begin{array}{c}4 \\ 5 \\ 11 \\ 6\end{array}\right);

(h)

A=(86523321423135117452),b=(211081518)A=\left(\begin{array}{cccc}8 & 6 & 5 & 2 \\ 3 & 3 & 2 & 1 \\ 4 & 2 & 3 & 1 \\ 3 & 5 & 1 & 1 \\ 7 & 4 & 5 & 2\end{array}\right), \quad b=\left(\begin{array}{c}21 \\ 10 \\ 8 \\ 15 \\ 18\end{array}\right).

Problem 8.4

Find the general solution and a fundamental system of solutions of the system of equations:

?
(a)

{x1+x2−2x3+2x4=0,3x1+5x2+6x3−4x4=0,4x1+5x2−2x3+3x4=0,3x1+8x2+24x3−19x4=0;\begin{cases} x_{1}+x_{2}-2 x_{3}+2 x_{4}=0, \\ 3 x_{1}+5 x_{2}+6 x_{3}-4 x_{4}=0, \\ 4 x_{1}+5 x_{2}-2 x_{3}+3 x_{4}=0, \\ 3 x_{1}+8 x_{2}+24 x_{3}-19 x_{4}=0 ; \end{cases}

(b)

{x1−x3=0,x2−x4=0,−x1+x3−x5=0,−x2+x4−x6=0,−x3+x5=0,−x4+x6=0;\begin{cases} x_{1}-x_{3}=0, \\ x_{2}-x_{4}=0, \\ -x_{1}+x_{3}-x_{5}=0, \\ -x_{2}+x_{4}-x_{6}=0, \\ -x_{3}+x_{5}=0, \\ -x_{4}+x_{6}=0 ; \end{cases}

(c)

{x1−x3+x5=0,x2−x4+x6=0,x1−x2+x5−x6=0,x2−x3+x6=0,x1−x4+x5=0;\begin{cases} x_{1}-x_{3}+x_{5}=0, \\ x_{2}-x_{4}+x_{6}=0, \\ x_{1}-x_{2}+x_{5}-x_{6}=0, \\ x_{2}-x_{3}+x_{6}=0, \\ x_{1}-x_{4}+x_{5}=0 ; \end{cases}

(d)

{x1+x2=0,x1+x2+x3=0,x2+x3+x4=0,………………xn−2+xn−1+xn=0,xn−1+xn=0.\begin{cases} x_{1}+x_{2}=0, \\ x_{1}+x_{2}+x_{3}=0, \\ x_{2}+x_{3}+x_{4}=0, \\ \ldots \ldots \ldots \ldots \ldots \ldots \\ x_{n-2}+x_{n-1}+x_{n}=0, \\ x_{n-1}+x_{n}=0. \end{cases}

Problem 8.5

Find some basis of the kernel of the linear mapping given by the matrix:

?
(a)

(35−4224−631117−84)\left(\begin{array}{rrrr}3 & 5 & -4 & 2 \\ 2 & 4 & -6 & 3 \\ 11 & 17 & -8 & 4\end{array}\right);

(b)

(35321576437996548320)\left(\begin{array}{lllll}3 & 5 & 3 & 2 & 1 \\ 5 & 7 & 6 & 4 & 3 \\ 7 & 9 & 9 & 6 & 5 \\ 4 & 8 & 3 & 2 & 0\end{array}\right);

(c)

(692−411574253)\left(\begin{array}{rrr}6 & 9 & 2 \\ -4 & 1 & 1 \\ 5 & 7 & 4 \\ 2 & 5 & 3\end{array}\right);

(d)

(576−22899−34716−264−13−14)\left(\begin{array}{rrrrr}5 & 7 & 6 & -2 & 2 \\ 8 & 9 & 9 & -3 & 4 \\ 7 & 1 & 6 & -2 & 6 \\ 4 & -1 & 3 & -1 & 4\end{array}\right);

(e)

(56−27423−14279−35659−316)\left(\begin{array}{lllll}5 & 6 & -2 & 7 & 4 \\ 2 & 3 & -1 & 4 & 2 \\ 7 & 9 & -3 & 5 & 6 \\ 5 & 9 & -3 & 1 & 6\end{array}\right);

(f)

(341235713445215710165)\left(\begin{array}{rrrrr}3 & 4 & 1 & 2 & 3 \\ 5 & 7 & 1 & 3 & 4 \\ 4 & 5 & 2 & 1 & 5 \\ 7 & 10 & 1 & 6 & 5\end{array}\right).

Problem 8.6

Using Cramer's rule, solve the system of equations:

?
(a)

{2x1−x2=1,x1+16x2=17;\begin{cases} 2 x_{1}-x_{2}=1, \\ x_{1}+16 x_{2}=17 ; \end{cases}

(b)

{2x1+5x2=1,3x1+7x2=2;\begin{cases} 2 x_{1}+5 x_{2}=1, \\ 3 x_{1}+7 x_{2}=2 ; \end{cases}

(c)

{x1cos⁡α+x2sin⁡α=cos⁡β,−x1sin⁡α+x2cos⁡α=sin⁡β;\begin{cases} x_{1} \cos \alpha +x_{2} \sin \alpha =\cos \beta , \\ -x_{1} \sin \alpha +x_{2} \cos \alpha =\sin \beta ; \end{cases}

(d)

{2x1+x2+x3=3,x1+2x2+x3=0,x1+x2+2x3=0;\begin{cases} 2 x_{1}+x_{2}+x_{3}=3, \\ x_{1}+2 x_{2}+x_{3}=0, \\ x_{1}+x_{2}+2 x_{3}=0 ; \end{cases}

(e)

{x1+x2+x3=6,−x1+x2+x3=0,x1−x2+x3=2;\begin{cases} x_{1}+x_{2}+x_{3}=6, \\ -x_{1}+x_{2}+x_{3}=0, \\ x_{1}-x_{2}+x_{3}=2 ; \end{cases}

(f)

{2x1+3x2+5x3=10,3x1+7x2+4x3=3,x1+2x2+2x3=3.\begin{cases} 2 x_{1}+3 x_{2}+5 x_{3}=10, \\ 3 x_{1}+7 x_{2}+4 x_{3}=3, \\ x_{1}+2 x_{2}+2 x_{3}=3. \end{cases}

Problem 8.7

Find a polynomial f(x)f(x) of degree two with real coefficients such that f(1)=8,f(−1)=2,f(2)=14f(1)=8, \quad f(-1)=2, \quad f(2)=14.

?
Problem 8.8

Find a polynomial f(x)f(x) of degree three such that f(−2)=1,f(−1)=3,f(1)=13,f(2)=33f(-2)=1, \quad f(-1)=3, \quad f(1)=13, \quad f(2)=33.

?
Problem 8.9

Find a polynomial f(x)f(x) of degree four such that f(−3)=−77,f(−2)=−13,f(−1)=1,f(1)=−1,f(2)=−17f(-3)=-77, \quad f(-2)=-13, \quad f(-1)=1, \quad f(1)=-1, \quad f(2)=-17.

?
Problem 8.10

Solve the system of congruences:

?
(a)

{2x+y−z≡1,x+2y+z≡2,( mod 5);x+y−z≡−1\begin{cases} 2 x+y-z \equiv 1, \\ x+2 y+z \equiv 2,(\bmod 5) ; \\ x+y-z \equiv -1 \end{cases}

(b)

{3x+2y+5z≡1,2x+5y+3z≡1,5x+3y+2z≡4}\left\{ \begin{aligned} 3 x+2 y+5 z & \equiv 1, \\ 2 x+5 y+3 z & \equiv 1, \\ 5 x+3 y+2 z & \equiv 4\end{aligned}\right\}

Problem 8.11

Prove that if the determinant of a square matrix (aij)\left(a_{i j}\right) of order nn with integer entries is relatively prime to a natural number mm, then the system of congruences

(ai1x1+ai2+…+ain)≡bi( mod m),i=1,2,…,n, \left(a_{i 1} x_{1}+a_{i 2}+\ldots +a_{i n}\right) \equiv b_{i} \quad (\bmod m), \quad i=1,2, \ldots , n,

has a unique solution modulo mm.

?
Problem 8.12

Let AA be an integer matrix and let dd be the smallest of the absolute values of its entries. Prove that if, under integer elementary transformations of the rows and columns of AA, the number dd does not decrease, then dd divides all entries of the matrix AA.

?
Problem 8.13

Prove that, using elementary row and column transformations over the ring Z\mathbb {Z}, any integer matrix can be reduced to the form (A000)\left(\begin{array}{cc}A & 0 \\ 0 & 0\end{array}\right), where A=diag⁡{d1,…,dr}A=\operatorname {diag}\left\{ d_{1}, \ldots , d_{r}\right\} and di∣di+1d_{i} \mid d_{i+1}, (i=1,2,…,r−1)(i=1,2, \ldots , r-1).

?
Problem 8.14

Prove that if a square integer system of linear equations has a unique solution modulo every prime number pp, then it also has a unique solution over the ring of integers.

?
Problem 8.15

Determine whether a square integer system of linear equations that is consistent modulo every prime number pp is necessarily consistent over the ring of integers.

?
Problem 8.16

Prove that the following systems of equations have a unique solution modulo all primes except finitely many of them. Solve these systems modulo the remaining primes:

?
(a)

{x1+2x2+2x3=2,2x1+x2−2x3=1,2x1−2x2+x3=1;\begin{cases} x_{1}+2 x_{2}+2 x_{3}=2, \\ 2 x_{1}+x_{2}-2 x_{3}=1, \\ 2 x_{1}-2 x_{2}+x_{3}=1 ; \end{cases}

(b)

{x1+x2+x3=1,x1+x2+x4=1,x1+x3+x4=1,x2+x3+x4=1;\begin{cases} x_{1}+x_{2}+x_{3}=1, \\ x_{1}+x_{2}+x_{4}=1, \\ x_{1}+x_{3}+x_{4}=1, \\ x_{2}+x_{3}+x_{4}=1 ; \end{cases}

(c)

{x1+x2+x3+x4=1,x1+x2−x3−x4=1,x1+x2+x3−x4=1,x1−x2−x3+x4=0.\begin{cases} x_{1}+x_{2}+x_{3}+x_{4}=1, \\ x_{1}+x_{2}-x_{3}-x_{4}=1, \\ x_{1}+x_{2}+x_{3}-x_{4}=1, \\ x_{1}-x_{2}-x_{3}+x_{4}=0. \end{cases}

Problem 8.17

Prove that every system of linear equations with real coefficients can be reduced to echelon form using only elementary transformations of type II.

?
Problem 8.18

Prove that under integer elementary row and column transformations of an integer matrix, the greatest common divisor of its minors of a fixed order kk does not change.

?
Problem 8.19

Prove that if an integer matrix has been reduced, by integer elementary row and column transformations, to the form (A000)\left(\begin{array}{cc}A & 0 \\ 0 & 0\end{array}\right), where A=diag⁡{d1,d2,…,dr},di≠0A=\operatorname {diag}\left\{ d_{1}, d_{2}, \ldots , d_{r}\right\} , d_{i} \neq 0 and di∣di+1d_{i} \mid d_{i+1}, then the numbers d1,d2,…,drd_{1}, d_{2}, \ldots , d_{r} are uniquely determined (up to sign).

?
Problem 8.20

Two sets of unknowns are called integrally equivalent if they are related by

[y1⋮yn]=U[x1⋮xn], \left[\begin{smallmatrix} y_{1} \\ \vdots \\ y_{n} \end{smallmatrix}\right]=U\left[\begin{smallmatrix} x_{1} \\ \vdots \\ x_{n} \end{smallmatrix}\right],

where UU is an integer matrix whose determinant is equal, in absolute value, to 1. Prove that the system of equations

∑j=1naijxj=bi,i=1,2,…,m \sum _{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad i=1,2, \ldots , m

where aij,bia_{i j}, b_{i} are integers, is equivalent, over the ring of integers, to a system of equations of the form

diyi=ci,i=1,2,…,m d_{i} y_{i}=c_{i}, \quad i=1,2, \ldots , m

where the set of unknowns (y1,…,yn)\left(y_{1}, \ldots , y_{n}\right) is integrally equivalent to the set (x1,…,xn)\left(x_{1}, \ldots , x_{n}\right).

?
Problem 8.21

Prove that an integer system of equations has an integer solution if and only if, for every natural number kk, the greatest common divisors of all minors of order kk in the matrix of the system and in its augmented matrix coincide.

?
Problem 8.22

Prove that an integer system of equations has an integer solution if and only if it has a solution modulo every prime pp.

?
Problem 8.23

Justify the following practical method for finding all integer solutions of a system of equations

∑j=1naijxj=bi,i=1,2,…,m \sum _{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad i=1,2, \ldots , m

with integer coefficients. Construct the matrix (AbEn0)\left(\begin{array}{cc}A & b \\ E_{n} & 0\end{array}\right) of size (n+m)×(n+1)(n+m) \times (n+1). Then, using only integer elementary transformations of the first mm rows and nn columns, reduce this matrix to the form (DCU0)\left(\begin{array}{cc}D & C \\ U & 0\end{array}\right), where C=(c1⋮cm),∣det⁡U∣=1,D=(d10…00…00d2…00…0…………………00…dr0…000…00…0…………………00…00…0)C=\left(\begin{array}{c}c_{1} \\ \vdots \\ c_{m}\end{array}\right), \quad \left|\operatorname {det} U\right|=1, \quad D=\left(\begin{array}{ccccccc}d_{1} & 0 & \ldots & 0 & 0 & \ldots & 0 \\ 0 & d_{2} & \ldots & 0 & 0 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & d_{r} & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0\end{array}\right), di∣di+1,d1≠0,…,dr≠0d_{i} \mid d_{i+1}, \quad d_{1} \neq 0, \ldots , d_{r} \neq 0. Then the system is consistent if

di∣ci for i=1,…,r,ck=0 for k>r, \begin{gathered} d_{i} \mid c_{i} \quad \text{ for } \quad i=1, \ldots , r, \\ c_{k}=0 \quad \text{ for } \quad k>r, \end{gathered}

and the general solution is given by the formula

[x1⋮xn]=U[c1/d1⋮cr/dryr+1⋮yn] \left[\begin{smallmatrix} x_{1} \\ \vdots \\ x_{n} \end{smallmatrix}\right]=U\left[\begin{smallmatrix} c_{1} / d_{1} \\ \vdots \\ c_{r} / d_{r} \\ y_{r+1} \\ \vdots \\ y_{n} \end{smallmatrix}\right]

where yr+1,yr+2,…,yny_{r+1}, y_{r+2}, \ldots , y_{n} are arbitrary integers.

?
Problem 8.24

Find all integer solutions of the following systems of equations:

?
(a)

2x1+3x2+4x3=52 x_{1}+3 x_{2}+4 x_{3}=5;

(b)

{2x1+3x2−11x3−15x4=1,4x1−6x2+2x3+3x4=2,2x1−3x2+5x3+7x4=1.\begin{cases} 2 x_{1}+3 x_{2}-11 x_{3}-15 x_{4}=1, \\ 4 x_{1}-6 x_{2}+2 x_{3}+3 x_{4}=2, \\ 2 x_{1}-3 x_{2}+5 x_{3}+7 x_{4}=1. \end{cases}

Problem 8.25

Let AA and BB be matrices of the same size, such that the homogeneous systems of linear equations with matrices AA and BB are equivalent. Prove that one can pass from AA to BB by elementary row transformations.

?
Problem 8.26

Let a system of linear complex equations AX=bA X=b be given, with a square nonsingular matrix AA. Suppose that the sum of the absolute values of the entries in each row of the matrix E+AE+A is less than 1. Let X0X_{0} be an arbitrary column, and define inductively Xm+1=(A+E)Xm−bX_{m+1}=(A+E) X_{m}-b. Then the sequence of columns XmX_{m} converges to the solution of the equation AX=bA X=b.

?