The Number of Solutions of a System of Linear Equations

The standard form of a linear equation in n unknowns x_1,x_2,\dots ,x_n is

a_1x_1+a_2x_2+\dots +a_nx_n=b,

where a_1,a_2,\dots ,a_n and b are constants.

Here constants mean some real numbers (these constants may come from any number field).

A collection of one or more linear equations of same variables is called a system of linear equations.

An ordered collection s_1,s_2,\dots ,s_n is called a solution of the above equation if while putting x_1=s_1,x_2=s_2,\dots and x_n=s_n, the equation satisfied. (An ordered collection of n quantities is called n-tuple.)

Let us now consider the following linear equation:

x+4y=5.

(1,1), (2,\frac{3}{4}), (3,\frac{1}{2}), (0,\frac{5}{4}), (-1,\frac{3}{2}), (9,-1), (\pi,\frac{5-\pi}{4}), (5-4\pi,\pi) are some solutions of this equation. Furthermore for any value of x we can find a value of y and reversely. That is, the equation has infinite number of solutions. But the equation 3z=7 has only one solution and 0y+0z=5 has no solution. These are very simple examples. In order to study difficult one we have to know some definitions and methods:

 

Image Source : Shutterstock

Image Source : Shutterstock

A linear equation is called degenerate if it is of the following form:

0x_1+0x_2+\dots +0x_n=b

Now (i) if b\neq 0, then we get a contradiction, since the equation implies 0=b. Therefore if b\neq 0 the equation has no solution,

and (ii) if b=0, then the equation becomes 0x_1+0x_2+\dots +0x_n=0, which is always true. This means every n-tuple is solution of a the degenerate equation if b=0.

Thus the solution of degenerate equation depends on the constant b.

Therefore, if system of linear equations contains a degenerate equation with the constant b, then

(i) if b\neq 0, then the degenerate equation has no solution, so the system has no solution,

and (ii) if b=0, then every n-tuple is a solution of the degenerate equation, so the degenerate equation can not affect on the solution set of the system.

 

Let us next consider a linear equation in one unknown

ax=b.

If a=0, the equation becomes degenerate equation and from above discussion it is clear that the solution depends on b. That is, it has no solution if b\neq 0 and infinite number of solution if b=0.

And if a\neq 0, then x=\frac{b}{a} is the unique solution.

READ:   P v/s NP Problem

We have seen, a linear equation in one unknown has solution in any one of the following three possible ways:

(i) No solution

(ii) Infinitely many solutions

(iii) Single unique solution

 

Interestingly, every system of linear equations has solution in any one of the above three possible ways.

The next thing which we needed is the idea of linear combination of linear equations.

Consider the standard form of a system of linear equations with r equations in n unknowns:

a_{11}x_1+a_{12}x_2+\dots +a_{1n}x_n=b_1

a_{21}x_1+a_{22}x_2+\dots +a_{2n}x_n=b_2

\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots ________(A)

a_{r1}x_1+a_{r2}x_2+\dots +a_{rn}x_n=b_r

For any r scalars c_1,c_2,\dots c_r, consider the following equation:

c_1(a_{11}x_1+a_{12}x_2+\dots +a_{1n}x_n)+c_2(a_{21}x_1+a_{22}x_2+\dots +a_{2n}x_n)+\dots c_r(a_{r1}x_1+a_{r2}x_2+\dots +a_{rn}x_n)=c_1b_1+c_2b_2+\dots c_rb_r

Or (c_1a_{11}+c_2a_{21}+\dots +c_ra_{r1})x_1+(c_1a_{12}+c_2a_{22}+\dots +c_ra_{r2})x_2+\dots (c_1a_{1n}+c_2a_{2n}+\dots +c_ra_{nr})x_n=c_1b_1+c_2b_2+\dots c_rb_r.

Such an equation is called a linear combination of the above r equations.

 

Suppose, the above system contains no degenerate equation and any equation of the system is not a linear combination of some other equations of the system. Then

(i) if r<n, we can arbitrarily assign value to n-r variables and can obtain other r variables. That is, we will get infinitely many solutions.

(ii) if r=n, the system has a single unique solution. It can be proved by eliminating unknowns in such a way that the new system is an equivalent system of the previous system.

(iii) if r data-recalc-dims=n," /> the system has no solution.

 

Problems:

 

1) Consider the following system of equations:

2x+4y+3z=9

11x+2y+9z=2

3x+2y+3z=4

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

2) Consider the following system of equations:

2x+4y+3z=9

11x+2y+9z=2

3x+2y+3z=0

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

3) Consider the following system of equations:

2x+4y+3z=0

11x+2y+9z=0

3x+2y+3z=0

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

4) Consider the following system of equations:

2x+4y+3z=9

11x+2y+9z=2

3x+2y+3z=4

5x-2y+3z=4

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

5) Consider the following system of equations:

READ:   Algorithms: An Introduction

2x+4y+3z=9

11x+2y+9z=2

3x+2y+3z=4

5x-2y+3z=-6

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

6) Consider the following system of equations:

2x+4y+3z=9

11x+2y+9z=2

3x+2y+3z=4

5x+2y+3z=-6

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

7) Consider the following system of equations:

2x+4y+3z=9

11x+2y+9z=2

3x-2y+3z=4

5x+2y+3z=-6

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

8) Consider the following system of equations:

2x+4y+3z=9

10x+2y+9z=2

6x+4y+3z=5

4x+2y+3z=4

The system has

A) unique solution B) no solution

C) finitely many solutions D) infinitely many solutions

 

9) Consider the following system of two nondegenerate equations:

a_1x+b_1y=c_1

a_2x+b_2y=c_2.

Which of the following are true?

A) If the system has unique solution, then \frac{a_1}{a_2}\neq \frac{b_1}{b_2}.

B) If the system has no solution, then \frac{a_1}{a_2}=\frac{b_1}{b_2}=\frac{c_1}{c_2}.

C) If the system has no solution, then \frac{a_1}{a_2}=\frac{b_1}{b_2}\neq \frac{c_1}{c_2}.

D) If the system has no solution, then \frac{a_1}{a_2}\neq \frac{b_1}{b_2}=\frac{c_1}{c_2}.

E) If the system has infinite number of solutions, then \frac{a_1}{a_2}=\frac{b_1}{b_2}\neq \frac{c_1}{c_2}.

F) If the system has infinite number of solutions, then \frac{a_1}{a_2}=\frac{b_1}{b_2}=\frac{c_1}{c_2}.

 

10) Consider the following system of equations:

u+2v-3w+4x=0

2u-3v+5w-7x=0

5u+6v-9w+8x=0

Which of the following are true?

A) The system has a zero solution B) The system has only the zero solution

C) The system must have a non-zero solutions D) The system has infinitely many solutions

 

11) Consider the following system of equations in two unknowns x and y :

x+py=4

px+4y=q

For which value of p does the system has a unique solution?

A) 2 B) -2 C) for all value of p except \pm 2 D) \pm 2 E) \frac{q}{4}

 

12) Consider the following system of equations in two unknowns x and y :

x+py=4

px+4y=p

Which of the following statements are true?

A) The system may have infinite number of solutions.

B) The system cannot have infinite number of solutions.

C) The system may have no solution.

 

Answers to the problems:-

1) D , 2) A , 3) D , 4) B , 5) D , 6) A , 7) A , 8) B , 9) A, C & F , 10) A, C & D , 11) C , 12) B & C

READ:   Informatics Olympiads
The following two tabs change content below.

Pankaj Jyoti Mahanta

No Comments

Sorry, the comment form is closed at this time.