Skip to content
Glacius
Linear algebraConcept reference

Gaussian elimination

Elimination replaces an equation with a row combination that makes a selected variable coefficient zero.

1 min read1 figureSources & further reading
On this page 7 sections
  1. Overview
  2. Elimination makes one variable’s coefficient zero
  3. Choose a multiple that cancels the target coefficient
  4. Apply the chosen multiple to every entry in the target row; keep the source row
  5. Key takeaway
  6. Sources & further reading
  7. Concept connections

01Elimination makes one variable’s coefficient zero#

Elimination makes one variable’s coefficient zero. For x+2y=7x+2y=7 and 3x+y=83x+y=8, subtract three copies of the first equation from the second.

Use R2←R2−3R1R_2\leftarrow R_2-3R_1. The new coefficients are 3−3(1)=03-3(1)=0 and 1−3(2)=−51-3(2)=-5. The right side is 8−3(7)=−138-3(7)=-13.

Before rows are [1, 2, 7] and [3, 1, 8]; the last entry of each row is the right-hand constant. Operation R₂ ← R₂ − 3R₁ leaves row 1 unchanged and replaces row 2 with [0, -5, -13]. Every entry, including the constant, is updated.Before rows are [1, 2, 7] and [3, 1, 8]; the last entry of each row is the right-hand constant. Operation R₂ ← R₂ − 3R₁ leaves row 1 unchanged and replaces row 2 with [0, -5, -13]. Every entry, including the constant, is updated.
Figure 1Before rows are [1, 2, 7] and [3, 1, 8]; the last entry of each row is the right-hand constant. Operation R₂ ← R₂ − 3R₁ leaves row 1 unchanged and replaces row 2 with [0, -5, -13]. Every entry, including the constant, is updated.
Link to this figure ↗Download SVGDownload PNG
Check your reasoning

Order (x,y)(x,y). Eliminate x from R2R_2 using R1R_1. New R2R_2? [113238]\left[\begin{array}{rr|r}1&1&3\\2&3&8\end{array}\right]

  1. A[012]\left[\begin{array}{rr|r}0&1&2\end{array}\right]
  2. B[018]\left[\begin{array}{rr|r}0&1&8\end{array}\right]
  3. C[4514]\left[\begin{array}{rr|r}4&5&14\end{array}\right]
Show answer and explanation
[012]\left[\begin{array}{rr|r}0&1&2\end{array}\right]

Use R2−2R1R_2-2R_1.

02Choose a multiple that cancels the target coefficient#

Choose a multiple that cancels the target coefficient. If the source coefficient is 2 and the target is 6, subtract 3 source rows. If they are 1 and −2, add 2 source rows. A zero source coefficient cannot cancel a nonzero target.

Check your reasoning

Order (x,y)(x,y). Eliminate x from R2R_2 using R1R_1. New right side? [124315]\left[\begin{array}{rr|r}1&2&4\\3&1&5\end{array}\right]

Show answer and explanation
-7

Apply the same subtraction: 5−3(4)=−75-3(4)=-7.

03Apply the chosen multiple to every entry in the target row; keep the source row#

Apply the chosen multiple to every entry in the target row; keep the source row. Once the selected coefficient is zero, that elimination step is done. Larger systems repeat this move on other rows and variables.

Check your reasoning

Unit prices (u,v)(u,v). Orders: (1,1) costs 4; (2,3) costs 10. Pairs give quantities. Eliminate u from the second.

  1. Av=10v=10
  2. B4u+5v=184u+5v=18
  3. Cv=2v=2
Show answer and explanation
v=2v=2

Use R2−2R1R_2-2R_1.

Key takeaway

Cancel the coefficient and update every other entry, including the constant.

  • Eliminate a variable using elementary row operations.

Sources & further reading

  1. [1]

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Gaussian elimination.” Math behind ML. /learn/la-elimination