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}.$ Tags:
