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 \leq \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\leq\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.

$\begin{pmatrix}2&-1&3&-2&4\\4&-2&5&1&7\\2&-1&1&8&2\end{pmatrix}$

Solution:

$\begin{pmatrix}2&-1&3&-2&4\\4&-2&5&1&7\\2&-1&1&8&2\end{pmatrix}$

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

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

$\begin{vmatrix}2&-1&-2\\4&-2&1\\2&-1&8\end{vmatrix}=-32+8-2-8+2+32=0;$

$\begin{vmatrix}2&-1&4\\4&-2&7\\2&-1&2\end{vmatrix}=-8-16-14+16+14+8=0;$

$\begin{vmatrix}-1&3&-2\\-2&5&1\\-1&1&8\end{vmatrix}=-40+4-3-10+1+48=0;$

$\begin{vmatrix}-1&3&4\\-2&5&7\\-1&1&2\end{vmatrix}=-10-8-21+20+7+12=0;$

$\begin{vmatrix}-1&-2&4\\-2&1&7\\-1&8&2\end{vmatrix}=-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

$\begin{pmatrix}25&31&17&43\\75&94&53&132\\75&94&54&134\\25&32&20&48\end{pmatrix}$

Solution.

By successively applying elementary row operations, we have

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

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

$\begin{pmatrix}25&31&17&43\\0&1&2&3\\0&0&1&2\\0&1&3&5\end{pmatrix}\sim$ Subtract the second and third rows from the fourth:

$\begin{pmatrix}25&31&17&43\\0&1&2&3\\0&0&1&2\\0&0&0&0\end{pmatrix}\sim$ Subtract twice the third column from the fourth column:

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

$\begin{pmatrix}1&0&17&9\\0&1&2&-1\\0&0&1&0\\0&0&0&0\end{pmatrix}\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:

$\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&0\end{pmatrix}.$ 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

$\begin{pmatrix}47&-67&35&201&155\\26&98&23&-294&86\\16&-428&1&1284&52\end{pmatrix}$

Solution of homogeneous systems of equations.

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

$$\left\{\begin{array}{lcl}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}\right.$$

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

$A=\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...&...&...&...\\a_{m1}&a_{m2}&...&a_{mn}\end{pmatrix};$ $B=\begin{pmatrix}b_1\\b_2\\...\\b_m\end{pmatrix}.$

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\leq r\leq\min(m, n))$ rows and columns of matrix $A$. Discarding the last $m-r$ equations of the system, we obtain the shortened system: $$\left\{\begin{array}{lcl}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}\right.$$ 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:

$$\left\{\begin{array}{lcl}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}\right.$$ 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})= $ $\begin{pmatrix}x_1(c_1,...,c_{n-r})\\ \vdots\\x_r(c_1,...,c_{n-r})\\c_1\\ \vdots\\c_{n-r}\end{pmatrix}$. 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. $$\left\{\begin{array}{lcl}x_1+2x_2-x_3=0\\ 2x_1+9x_2-3x_3=0\end{array}\right.$$

Solution.

The coefficient matrix $A=\begin{pmatrix}1&2&-1\\2&9&-3\end{pmatrix}$ has rank 2.

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

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

$\Delta=\begin{vmatrix}1&2\\2&9\end{vmatrix}=9-4=5;$

$\Delta_1=\begin{vmatrix}c_1&2\\3c_1&9\end{vmatrix}=9c_1-6c_1=3c_1;$

$\Delta_2=\begin{vmatrix}1&c_1\\2&3c_1\end{vmatrix}=3c_1-2c_1=c_1;$

$x_1=\frac{\Delta_1}{\Delta}=\frac{3c_1}{5};$ $x_2=\frac{\Delta_2}{\Delta}=\frac{c_1}{5}.$

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

From the general solution, we find the fundamental solution set: $E_1=X(1)=\begin{pmatrix}\frac{3}{5}\\\frac{1}{5}\\1\end{pmatrix}.$ 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)=\begin{pmatrix}3\\1\\5\end{pmatrix}.$

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

Answer: $X(c_1)=c_1E_1;$ $E_1=\begin{pmatrix}3\\1\\5\end{pmatrix}.$

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

Solution.

The coefficient matrix $A=\begin{pmatrix}3&2&1\\2&5&3\\3&4&2\end{pmatrix}$ has a rank of 3, because $det A=\begin{vmatrix}3&2&1\\2&5&3\\3&4&2\end{vmatrix}=$ $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\neq 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. $$\left\{\begin{array}{lcl}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}\right.$$

Solution.

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

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

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

$\begin{vmatrix}1&2&-3\\3&5&-4\\4&5&3\end{vmatrix}=15-45-32+60+20-18=0;$

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

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

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

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

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

$\Delta=\begin{vmatrix}1&2\\3&5\end{vmatrix}=5-6=-1;$

$\Delta_1=\begin{vmatrix}-4c_1+3c_2&2\\-6c_1+4c_2&5\end{vmatrix}=-20c_1+15c_2+12c_1-8c_2=-8c_1+7c_2;$

$\Delta_2=\begin{vmatrix}1&-4c_1+3c_2\\3&-6c_1+4c_2\end{vmatrix}=-6c_1+4c_2+12c_1-9c_2=6c_1-5c_2;$

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

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

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

Using the fundamental solution set, the general solution can be expressed as$X(c_1, c_2)=c_1E_1+c_2E_2.$

Answer: $X(c_1, c_2)=c_1E_1+c_2E_2;$ $E_1=\begin{pmatrix}8\\-6\\1\\0\end{pmatrix},$ $E_2=\begin{pmatrix}-7\\5\\0\\1\end{pmatrix}.$

Homework:

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

$\begin{pmatrix}1&3&5&-1\\2&-1&-3&4\\5&1&-1&7\\7&7&9&1\end{pmatrix}.$

Answer: 3.

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

$\begin{pmatrix}1&2&3&0&-1\\0&1&1&1&0\\1&3&4&1&-1\end{pmatrix}$

Answer: 2.

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

$\begin{pmatrix}24&19&36&72&-38\\49&40&73&147&-80\\73&59&98&219&-118\\47&36&71&141&-72\end{pmatrix}$

Answer: 3.

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

$\begin{pmatrix}-1&3&3&-4\\4&-7&-2&1\\-3&5&1&0\\-2&3&0&1\end{pmatrix}$

Answer: 2.

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

5. $$\left\{\begin{array}{lcl}x_1-2x_2-3x_3=0\\ -2x_1+4x_2+6x_3=0\end{array}\right.$$

Answer: $X(c_1, c_2)=c_1E_1+c_2E_2;$ $E_1=\begin{pmatrix}2\\1\\0\end{pmatrix}, $ $E_2=\begin{pmatrix}3\\0\\1\end{pmatrix}.$

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

Answer: $X(c_1)=c_1E_1;$ $E_1=\begin{pmatrix}4\\1\\-5\end{pmatrix}.$

7. $$\left\{\begin{array}{lcl}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}\right.$$

Answer: $X(c_1, c_2)=c_1E_1+c_2E_2;$ $E_1=\begin{pmatrix}1\\0\\-5/2\\7/2\end{pmatrix}, $ $E_2=\begin{pmatrix}0\\1\\5\\-7\end{pmatrix}.$