Gaussian elimination

For a system of linear equations, for example:

Now we want to solve this linear system of equations. What we can do is multiply one of the equations by a number, subtract from the other equation, cancel one variable, repeat the above steps and cancel the other variable. This method of solving a system of equations has been learned in junior high school. It is called "elimination".
For example, for the above system of equations, (1) + (2), eliminate the variables, get the new equation. Then multiply the new equation by 5, and then subtract the formula (3) to get the formula containing only x_3. Solved. Back againSolved。
This process is very simple, but think about what we did during the elimination process:

1. Row doubling transformation (multiply a row by a number and add it to another row)
2. Multiply transformation (multiply a row by a non-zero number)
3. Row exchange (swapping the positions of two rows): In our opinion, we do not use this transformation, but you can indeed exchange the positions of any two expressions during the elimination process, which is extremely important in matrix operations.

We call the above three transformationselementary row transformation, it can be seen that the elementary row transformation does not affect the solution set of the system of equations.

Next, we extract the coefficients of the system of equations and put them in the first box according to their original positions, and put the constants on the right side of the system of equations in the second box.

We call this list of numbers plus a box a matrix. For solving systems of linear equations we prefer the augmented matrix form. Consider if we treat each row of the matrix as an equation, and we perform elementary row transformations on these rows. Depending on the number and method of elementary row transformations we do, we will get many new matrices, and these matrices must have the same solution set as the original matrix.
Therefore, we say that if one matrix becomes another matrix after several elementary row transformations, we say that the two matrices are row equivalent. Row-equivalent matrices have exactly the same set of solutions.

In this way, elimination of the system of equations is converted into elimination of the matrix. In dealing with extremely large systems of equations and solution existence and uniqueness issues, the matrix elimination method is far more convenient than the traditional solution of systems of equations.

# Systematic solution to systems of equations—Gaussian elimination method

Convert the augmented matrix into the form of a ladder matrix through elementary row transformation:

is the leading element of each row of the ladder matrix, which we callmain element, the column where the pivot is located is calledmain column, the column with no pivot is calledfree column. The variable corresponding to the main column is calledbasic variables, the variable corresponding to the free column is calledFree variables.
Next, we transform theThe element at the pivot position is set to 1, and other elements in the main column except the pivot are set to 0.. The resulting matrix is ​​called a reduced row echelon matrix.

With the simplified row echelon matrix we know:

Solution:

This solution is called an explicit expression of the solution. As long as the values of the two free variables are determined, the solution to the system of equations is determined. Because there are free variables, this equation has countless solutions.

# Matrix equations and vector equations

For a system of equations:

We have two other expressions:
matrix equation：

Vector equation:

It can be seen that the product of a matrix and a vector is a linear combination of the column vectors in A weighted by the elements in X.
Vector operations

• Addition:
• Multiply numbers:
  Linear properties of matrices
  
  

# Implicit expression of solution: parameter vector form

For the explicit solution of the equation:

We can write it as free variableis a linear combination of weights

# Example questions

poj1222

//Gaussian elimination
#include<iostream>
#include<cstring>
using namespace std; int a[31][31];//Represents 30 equation systems
int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int res[5][6];//result void back () { for (int i = 29; i >= 0; i--) { res[i / 6][i % 6] = a[i][30]; }
} void gauss () { for (int i = 0; i < 30; i++) { //row swap int k = i; for (; k < 30; k++) { if (a[k][i]) break; } for (int j = 0; j <= 30; j++) {//att1: There is a unique solution according to the meaning of the question, so k will not >= 30 here. No need to judge anymore. swap(a[i][j], a[k][j]); } //Elimination--convert into unit matrix for (int j = 0; j < 30; j++) {//att1: starts from 0 if (i == j) continue;//att2: Don’t miss it if (a[j][i]) { for (int k = i; k <= 30; k++) { a[j][k] ^= a[i][k]; } } } } back();
} int main()
{ int t, cnt = 0; cin >> t; while (t--) { memset(a, 0, sizeof(a)); for (int i = 0; i < 30; i++) { cin >> a[i][30]; } for (int i = 0; i < 5; i++) { for (int j = 0; j < 6; j++) { int ti = i * 6 + j; for (int k = 0; k < 5; k++) { int tx = i + d[k][0]; int ty = j + d[k][1]; if (tx < 0 || tx > 4 || ty < 0 || ty > 5) continue; a[ti][tx * 6 + ty] = 1; } } } gauss(); cout << "PUZZLE #" << ++cnt << endl; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { cout << res[i][j] << ' '; } cout << res[i][5] << endl; } } return 0;
}