StatLect
Index > Matrix algebra

Equivalent systems of equations

Two systems of linear equations are equivalent if and only if they have the same set of solutions. In other words, two systems are equivalent if and only if every solution of one of them is also a solution of the other.

All the main methods used to solve linear systems are based on the same principle: given a system, we transform it into an equivalent system that is easier to solve; then, its solution is also the solution of the original system.

Table of Contents

Definition

Remember that a system of K equations in $L$ unknowns can be written in matrix form as[eq1]where A is the $K	imes L$ matrix of coefficients of the system, $b$ is the Kx1 vector of constants and x is the $L	imes 1$ vector of unknowns.

Definition Let [eq2]and[eq3]be two linear systems, both having an $L	imes 1$ vector of unknowns x. The two systems are equivalent if and only if they have the same solutions, that is, if and only if[eq4]

How to transform a system into an equivalent one

A system of equations can be transformed into an equivalent one by pre-multiplying both sides of its matrix form by an invertible matrix.

Proposition The system of K equations in $L$ unknowns[eq5]is equivalent to the system[eq6]for any invertible $K	imes K$ matrix $R$.

Proof

Suppose x solves the system[eq7]that is, $Ax$ and $b$ are the same vector. Clearly, if we pre-multiply the same vector by the same matrix $R$, we obtain the same result. As a consequence, [eq8]which is the same as[eq6]Thus, we have proved that[eq10]Now, suppose x solves the system[eq6]We have assumed that $R$ is invertible, so that its inverse $R^{-1}$ exists. We can pre-multiply both sides of the last equation by $R^{-1}$ and obtain[eq12]or[eq13]Since $R^{-1}R=I$, we have[eq14]Thus, we have proved that[eq15]which, together with the implication derived previously, gives[eq16]that is, x is a solution of one of the two systems if and only if it is a solution of the other one. In other words, the two systems are equivalent.

Example Consider the system of two equations in two unknowns[eq17]The system can be written in matrix form as[eq18]where[eq19]If we multiply the first equation by $2$ and leave the second equation unchanged, we obtain a new system[eq20]The matrix form of the new system is[eq3]where[eq22]The new system is equivalent to the original one because the same result can be achieved by pre-multiplying the matrix form of the original system by the invertible matrix[eq23]In fact,[eq24]and[eq25]

The book

Most of the learning materials found on this website are now available in a traditional textbook format.