Elementary transformations. Matrix rank. Solving homogeneous systems of equations.

Elementary transformations of a matrix include the following:

1. Permuting rows (columns);

2. Multiplying a row (column) by a number different from zero;

3. Adding to the elements of one row (column) the corresponding elements of another row (column) multiplied by some number.

Let $A$ be an $m\times n$ matrix. Suppose we arbitrarily select $k$ rows and $k$ columns in $A$ $(k\le min(m,n)).$ The elements at the intersection of the selected rows and columns form a square matrix of order $k,$ whose determinant is called the minor of order $k$ of matrix $A.$

The main methods for computing the rank of a matrix are as follows:

Method of Bordering Minors: Let's say we find a non-zero minor of order $k$, denoted as $M$, within the matrix. We only consider those minors of order $(k+1)$ that contain (border) the minor $M$. If all of these $(k+1)$-order minors are zero, then the rank of the matrix is $k$. Otherwise, if among the bordering minors there exists a non-zero $(k+1)$-order minor, the procedure is repeated.

Method of Elementary Transformations: This method is based on the principle that elementary transformations of a matrix do not change its rank. By applying these transformations, the matrix can be brought to a form where all its elements except $a_{11},a_{22},...,a_{rr}$ $(r\le min(m,n))$ are zero. Consequently, the rank of the matrix is $r$.

Examples.

1. Find the rank of the matrix using the method of bordering minors.

$\left(\begin{array}{ccccc}2& -1& 3& -2& 4\\ 4& -2& 5& 1& 7\\ 2& -1& 1& 8& 2\end{array}\right)$

Solution:

$\left(\begin{array}{ccccc}2& -1& 3& -2& 4\\ 4& -2& 5& 1& 7\\ 2& -1& 1& 8& 2\end{array}\right)$

Fixing the non-zero minor of the second order: $M_2=\left|\begin{array}{cc}-1& 3\\ -2& 5\end{array}\right|=-5+6=1.$

Let's consider the bordering minors of the third order: $\left|\begin{array}{ccc}2& -1& 3\\ 4& -2& 5\\ 2& -1& 1\end{array}\right|=-4-12-10+12+10+4=0;$

$\left|\begin{array}{ccc}2& -1& -2\\ 4& -2& 1\\ 2& -1& 8\end{array}\right|=-32+8-2-8+2+32=0;$

$\left|\begin{array}{ccc}2& -1& 4\\ 4& -2& 7\\ 2& -1& 2\end{array}\right|=-8-16-14+16+14+8=0;$

$\left|\begin{array}{ccc}-1& 3& -2\\ -2& 5& 1\\ -1& 1& 8\end{array}\right|=-40+4-3-10+1+48=0;$

$\left|\begin{array}{ccc}-1& 3& 4\\ -2& 5& 7\\ -1& 1& 2\end{array}\right|=-10-8-21+20+7+12=0;$

$\left|\begin{array}{ccc}-1& -2& 4\\ -2& 1& 7\\ -1& 8& 2\end{array}\right|=-2-64+14+4+56-8=0.$

Thus, the rank of matrix $A$ is two.

Answer: 2.

2. Compute the rank of the matrix using elementary row operations

$\left(\begin{array}{cccc}25& 31& 17& 43\\ 75& 94& 53& 132\\ 75& 94& 54& 134\\ 25& 32& 20& 48\end{array}\right)$

Solution.

By successively applying elementary row operations, we have

$\left(\begin{array}{cccc}25& 31& 17& 43\\ 75& 94& 53& 132\\ 75& 94& 54& 134\\ 25& 32& 20& 48\end{array}\right)\sim$ Subtract the second row from the third, and the first row from the second:

$\left(\begin{array}{cccc}25& 31& 17& 43\\ 75& 94& 53& 132\\ 0& 0& 1& 2\\ 0& 1& 3& 5\end{array}\right)\sim$ Subtract three times the first row from the second:

$\left(\begin{array}{cccc}25& 31& 17& 43\\ 0& 1& 2& 3\\ 0& 0& 1& 2\\ 0& 1& 3& 5\end{array}\right)\sim$ Subtract the second and third rows from the fourth:

$\left(\begin{array}{cccc}25& 31& 17& 43\\ 0& 1& 2& 3\\ 0& 0& 1& 2\\ 0& 0& 0& 0\end{array}\right)\sim$ Subtract twice the third column from the fourth column:

$\left(\begin{array}{cccc}25& 31& 17& 9\\ 0& 1& 2& -1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right)\sim$Divide the first column by 25, and subtract 31 times the first column from the second:

$\left(\begin{array}{cccc}1& 0& 17& 9\\ 0& 1& 2& -1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right)\sim$ Subtract 17 times the first column and 2 times the second column from the third, and subtract 9 times the first column and 2 times the second column from the fourth, then add 2 times the second column to the fourth:

$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right).$ The rank of the last matrix is three. Therefore, the original matrix has the same rank.

Answer: 3.

3. Compute the rank of the matrix using elementary row operations

$\left(\begin{array}{ccccc}47& -67& 35& 201& 155\\ 26& 98& 23& -294& 86\\ 16& -428& 1& 1284& 52\end{array}\right)$

Solution of homogeneous systems of equations.

Let's consider a system of $m$ linear equations with $n$ unknowns of the general form:

$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n=b_2\\ ...............................\\ a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n=b_m\end{array}$$

or, in matrix form, $AX=B$, where

$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ ...& ...& ...& ...\\ a_{m1}& a_{m2}& ...& a_{mn}\end{array}\right);$ $B=\left(\begin{array}{c}{b}_1\\ b_2\\ ...\\ b_m\end{array}\right).$

If $B=0$, then the system is called homogeneous. Otherwise, it is called non-homogeneous.

A system is called consistent if it has at least one solution. Otherwise, the system is inconsistent.

The homogeneous system $AX=0$ is always consistent since it has the trivial solution $X=0$. For the existence of a non-trivial solution, it is necessary and sufficient for $r=\text{rank} A

Let $r=\text{rank}A$. Without loss of generality, we assume that the basic minor is located in the first $r$ $(1\le r\le min(m,n))$ rows and columns of matrix $A$. Discarding the last $m-r$ equations of the system, we obtain the shortened system: $$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n=b_2\\ ...............................\\ a_{r1}{x}_1+a_{r2}{x}_2+...+a_{rn}{x}_n=b_r\end{array}$$ which is equivalent to the original. We will call the unknowns $x_1,x_2,...,x_r$ basic, and $x_{r+1},x_{r+2},...,x_n$ - free, and move the terms containing the free variables to the right-hand side of the equations. We obtain a system of equations relative to basic unknowns:

$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1r}{x}_r=b_1-a_{1,r+1}{x}_{r+1}-...-a_{1n}{x}_n\\ a_{21}{x}_1+a_{22}{x}_2+...+a_{2r}{x}_r=b_2-a_{2,r+1}{x}_{r+1}-...-a_{2n}{x}_n\\ ...............................\\ a_{r1}{x}_1+a_{r2}{x}_2+...+a_{rr}{x}_r=b_r-a_{r,r+1}{x}_{r+1}-...-a_{rn}{x}_n\end{array}$$ which, for each set of values of the free variables $x_{r+1}=c_1,...,x_n=c_{n-r}$, has a unique solution $x_1(c_1,...,c_{n-r}),...,x_r(c_1,...,c_{n-r})$, found using Cramer's rule.

The corresponding solution to the shortened system, and therefore to the original system, has the form $X(c_1,...,c_{n-r})=$ $\left(\begin{array}{c}{x}_1(c_1,...,c_{n-r})\\ ⋮\\ x_r(c_1,...,c_{n-r})\\ c_1\\ ⋮\\ c_{n-r}\end{array}\right)$. This formula is called the general solution of the system.

The system of column vectors $E_1,...,E_{n-r}$, obtained by setting each free variable to 1 in turn and all others to 0, is called a fundamental solution system.

The general solution to a homogeneous system is of the form $X=c_1{E}_1+...+c_{n-r}{E}_{n-r}$.

Any linear combination of solutions to the homogeneous system of equations is also a solution.

Examples:

Find the fundamental solution system and the general solution to the following systems:

1. $$\{\begin{array}{l}{x}_1+2x_2-x_3=0\\ 2x_1+9x_2-3x_3=0\end{array}$$

Solution.

The coefficient matrix $A=\left(\begin{array}{ccc}1& 2& -1\\ 2& 9& -3\end{array}\right)$ has rank 2.

Let's choose the minor $M=\left|\begin{array}{cc}1& 2\\ 2& 9\end{array}\right|=9-4=5\ne 0$ as the basic minor. Then, setting $x_3=c_1$, we obtain:

$$\{\begin{array}{l}{x}_1+2x_2={с}_1\\ 2x_1+9x_2=3{с}_1\end{array}$$ Using Cramer's rule, we find $x_1$ and $x_2:$

$\mathrm{\Delta }=\left|\begin{array}{cc}1& 2\\ 2& 9\end{array}\right|=9-4=5;$

${\mathrm{\Delta }}_1=\left|\begin{array}{cc}{c}_1& 2\\ 3c_1& 9\end{array}\right|=9c_1-6c_1=3c_1;$

${\mathrm{\Delta }}_2=\left|\begin{array}{cc}1& c_1\\ 2& 3c_1\end{array}\right|=3c_1-2c_1=c_1;$

$x_1=\frac{{\mathrm{\Delta }}_1}{\mathrm{\Delta }}=\frac{3c_1}{5};$ $x_2=\frac{{\mathrm{\Delta }}_2}{\mathrm{\Delta }}=\frac{c_1}{5}.$

Thus, the general solution of the system $X(c_1)=\left(\begin{array}{c}\frac{3c_1}{5}\\ \frac{c_1}{5}\\ c_1\end{array}\right).$

From the general solution, we find the fundamental solution set: $E_1=X(1)=\left(\begin{array}{c}\frac{3}{5}\\ \frac{1}{5}\\ 1\end{array}\right).$ Since any linear combination of solutions of the homogeneous system of equations is also its solution, the fundamental solution set can also be expressed as $E_1=X(1)=\left(\begin{array}{c}3\\ 1\\ 5\end{array}\right).$

With the use of the fundamental solution set, the general solution can be expressed as$X(c_1)=c_1{E}_1.$

Answer: $X(c_1)=c_1{E}_1;$ $E_1=\left(\begin{array}{c}3\\ 1\\ 5\end{array}\right).$

2. $$\{\begin{array}{l}3x_1+2x_2+x_3=0\\ 2x_1+5x_2+3x_3=0\\ 3x_1+4x_2+2x_3=0\end{array}$$

Solution.

The coefficient matrix $A=\left(\begin{array}{ccc}3& 2& 1\\ 2& 5& 3\\ 3& 4& 2\end{array}\right)$ has a rank of 3, because $detA=\left|\begin{array}{ccc}3& 2& 1\\ 2& 5& 3\\ 3& 4& 2\end{array}\right|=$ $3\cdot 5\cdot 2+2\cdot 4\cdot 1+2\cdot 3\cdot 3-3\cdot 5\cdot 1-4\cdot 3\cdot 3-$ $-2\cdot 2\cdot 2=30+8+18-15-36-8=56-59=-3\ne 0.$

The system has only the trivial solution since the rank equals the number of unknowns.

Answer: The system has only the trivial solution.

3. $$\{\begin{array}{l}{x}_1+2x_2+4x_3-3x_4=0\\ 3x_1+5x_2+6x_3-4x_4=0\\ 4x_1+5x_2-2x_3+3x_4=0\\ 3x_1+8x_2+24x_3-19x_4=0\end{array}$$

Solution.

Let's calculate the rank of the coefficient matrix $A=\left(\begin{array}{cccc}1& 2& 4& -3\\ 3& 5& 6& -4\\ 4& 5& -2& 3\\ 3& 8& 24& -19\end{array}\right)$ using the method of surrounding minors:

We fix a non-zero minor of the second order $M_2=\left|\begin{array}{cc}1& 2\\ 3& 5\end{array}\right|=5-6=-1$.

Now, let's consider the surrounding minors of the third order: $\left|\begin{array}{ccc}1& 2& 4\\ 3& 5& 6\\ 4& 5& -2\end{array}\right|=-10+60+48-80-30+12=0;$

$\left|\begin{array}{ccc}1& 2& -3\\ 3& 5& -4\\ 4& 5& 3\end{array}\right|=15-45-32+60+20-18=0;$

$\left|\begin{array}{ccc}1& 2& 4\\ 3& 5& 6\\ 3& 8& 24\end{array}\right|=120+96+36-60-48-144=0;$

$\left|\begin{array}{ccc}1& 2& -3\\ 3& 5& -4\\ 3& 8& -19\end{array}\right|=-95-72-24+45+32+114=0;$

Therefore, the rank of the matrix $A$ is equal to two.

Let's choose the minor $M=\left|\begin{array}{cc}1& 2\\ 3& 5\end{array}\right|=5-6=-1\ne 0$ as the basis minor. Then, assuming $x_3=c_1$ and $x_4=c_2$, we get: $$\{\begin{array}{l}{x}_1+2x_2=-4c_1+3c_2\\ 3x_1+5x_2=-6c_1+4c_2\end{array}$$

By using Cramer's rule, we find $x_1$ and $x_2$:

$\mathrm{\Delta }=\left|\begin{array}{cc}1& 2\\ 3& 5\end{array}\right|=5-6=-1;$

${\mathrm{\Delta }}_1=\left|\begin{array}{cc}-4c_1+3c_2& 2\\ -6c_1+4c_2& 5\end{array}\right|=-20c_1+15c_2+12c_1-8c_2=-8c_1+7c_2;$

${\mathrm{\Delta }}_2=\left|\begin{array}{cc}1& -4c_1+3c_2\\ 3& -6c_1+4c_2\end{array}\right|=-6c_1+4c_2+12c_1-9c_2=6c_1-5c_2;$

$x_1=\frac{{\mathrm{\Delta }}_1}{\mathrm{\Delta }}=\frac{-8c_1+7c_2}{-1}=8c_1-7c_2;$ $x_2=\frac{{\mathrm{\Delta }}_2}{\mathrm{\Delta }}=\frac{6c_1-5c_2}{-1}=-6c_1+5c_2.$

Therefore, the general solution of the system is:$X(c_1,c_2)=\left(\begin{array}{c}8c_1-7c_2\\ -6c_1+5c_2\\ c_1\\ c_2\end{array}\right).$

From the general solution, we find the fundamental solution set: $E_1=X(1,0)=\left(\begin{array}{c}8\\ -6\\ 1\\ 0\end{array}\right),$ $E_2=X(0,1)=\left(\begin{array}{c}-7\\ 5\\ 0\\ 1\end{array}\right).$

Using the fundamental solution set, the general solution can be expressed as$X(c_1,c_2)=c_1{E}_1+c_2{E}_2.$

Answer: $X(c_1,c_2)=c_1{E}_1+c_2{E}_2;$ $E_1=\left(\begin{array}{c}8\\ -6\\ 1\\ 0\end{array}\right),$ $E_2=\left(\begin{array}{c}-7\\ 5\\ 0\\ 1\end{array}\right).$

Homework:

1. Find the rank of the matrix using the method of determinant minors.

$\left(\begin{array}{cccc}1& 3& 5& -1\\ 2& -1& -3& 4\\ 5& 1& -1& 7\\ 7& 7& 9& 1\end{array}\right).$

Answer: 3.

2. Find the rank of the matrix using the method of bounding minors.

$\left(\begin{array}{ccccc}1& 2& 3& 0& -1\\ 0& 1& 1& 1& 0\\ 1& 3& 4& 1& -1\end{array}\right)$

Answer: 2.

3. Compute the rank of the matrix using the method of elementary transformations.

$\left(\begin{array}{ccccc}24& 19& 36& 72& -38\\ 49& 40& 73& 147& -80\\ 73& 59& 98& 219& -118\\ 47& 36& 71& 141& -72\end{array}\right)$

Answer: 3.

4. Compute the rank of the matrix using the method of elementary transformations

$\left(\begin{array}{cccc}-1& 3& 3& -4\\ 4& -7& -2& 1\\ -3& 5& 1& 0\\ -2& 3& 0& 1\end{array}\right)$

Answer: 2.

Find the fundamental solution set and the general solution of the following systems:

5. $$\{\begin{array}{l}{x}_1-2x_2-3x_3=0\\ -2x_1+4x_2+6x_3=0\end{array}$$

Answer: $X(c_1,c_2)=c_1{E}_1+c_2{E}_2;$ $E_1=\left(\begin{array}{c}2\\ 1\\ 0\end{array}\right),$ $E_2=\left(\begin{array}{c}3\\ 0\\ 1\end{array}\right).$

6. $$\{\begin{array}{l}2x_1-3x_2+x_3=0\\ x_1+x_2+x_3=0\\ 3x_1-2x_2+2x_3=0\end{array}$$

Answer: $X(c_1)=c_1{E}_1;$ $E_1=\left(\begin{array}{c}4\\ 1\\ -5\end{array}\right).$

7. $$\{\begin{array}{l}2x_1-4x_2+5x_3+3x_4=0\\ 3x_1-6x_2+4x_3+2x_4=0\\ 4x_1-8x_2+17x_3+11x_4=0\end{array}$$

Answer: $X(c_1,c_2)=c_1{E}_1+c_2{E}_2;$ $E_1=\left(\begin{array}{c}1\\ 0\\ -5/2\\ 7/2\end{array}\right),$ $E_2=\left(\begin{array}{c}0\\ 1\\ 5\\ -7\end{array}\right).$

Tags: linear algebra, matrix, matrix rank, method of elementary transformations