Linear system of equations with non-trivial solutions

In summary, the proof uses mathematical induction to show that a system of linear equations with m equations in n unknowns, where n > m, has a non-trivial solution. The proof involves subtracting a multiple of the first equation from the others to eliminate one unknown, and then using the assumption that the theorem is true for m-1 equations in n-1 unknowns to find a solution for the original system. This strategy is similar to Fermat's method of "infinite descent."
  • #1
converge
2
0

Homework Statement



Let

[itex](**)[/itex]


\begin{matrix}
a_{11}x_1 & + & \ldots & + & a_{1n}x_n & = 0 \\
\vdots & & & & \vdots\\
a_{m1}x_1 & + & \ldots & + & a_{mn}x_n & = 0 \\
\end{matrix}


be a system of [itex]m[/itex] linear equations in [itex]n[/itex] unknowns, and assume that
[itex]n > m[/itex]. Then the system has a non-trivial solution.

[itex]Proof:[/itex]

Consider first the case of one equation in [itex]n[/itex] unknowns, [itex]n > 1[/itex]:

[itex]a_{1}x_1 + \ldots + a_{n}x_n = 0[/itex]
If all coefficients [itex]a_1, \ldots, a_n[/itex] are equal to [itex]0[/itex], then any value of the variables
will be a solution, and a non-trivial solution certainly exists. Suppose
that some coefficient [itex]a_i \neq 0[/itex]. After renumbering the variables and the
coefficients, we may assume that it is [itex]a_i[/itex] Then we give [itex]x_2, \ldots, x_n[/itex] arbitrary
values, for instance we let [itex]x_2, \ldots, x_n = 1[/itex] and solve for [itex]x_1[/itex] letting

[itex]x_1 = \frac {-1}{a_1} (a_2 + \ldots + a_n)[/itex]

In that manner, we obtain a non-trivial solution for our system of equations.
Let us now assume that our theorem is true for a system of [itex]m - 1[/itex]
equations in more than [itex]m - 1[/itex] unknowns. We shall prove that it is true
for [itex]m[/itex] equations in [itex]n[/itex] unknowns when [itex]n > m[/itex]. We consider the system
[itex](**)[/itex].

If all coefficients [itex](a_{ij})[/itex] are equal to [itex]0[/itex], we can give any non-zero value
to our variables to get a solution. If some coefficient is not equal to [itex]0[/itex],
then after renumbering the equations and the variables, we may assume
that it is [itex]a_{11}[/itex]. We shall subtract a multiple of the first equation from the
others to eliminate [itex]x_1[/itex]. Namely, we consider the system of equations

[itex] (A_2 - \frac {a_{21}}{a_{11}} A_1) \cdot X [/itex]

[itex] (A_m - \frac {a_{m1}}{a_{11}} A_1) \cdot X [/itex]


Which can be written also in the form

[itex](***)[/itex]

[itex]A_2 \cdot X - \frac {a_{21}}{a_{11}} A_1 \cdot X = 0[/itex]

[itex]\vdots[/itex]

[itex] A_m \cdot X - \frac {a_{m1}}{a_{11}} A_1 \cdot X = 0[/itex]

In this system, the coefficient of [itex]x_1[/itex] is equal to [itex]0[/itex]. Hence we may view
[itex](***)[/itex]as a system of [itex]m - 1[/itex] equations in [itex]n - 1[/itex] unknowns, and we have
[itex]n-1 > m-1[/itex].

According to our assumption, we can find a non-trivial solution
[itex](x_2, ... ,x_n)[/itex] for this system. We can then solve for [itex]x_1[/itex] in the first equation,
namely

[itex]x_1 = \frac {-1}{a_{11}} (a_{12}x_2 + \ldots + a_{1n}x_n)[/itex].

In that way, we find a solution of [itex]A_1 \cdot X = 0[/itex]. But according to [itex](***)[/itex], we
have


[itex]A_i \cdot X = \frac {a_{i1}}{a_{11}} A_1 \cdot X[/itex]

for [itex]i = 2, \ldots ,m[/itex]. Hence [itex]A_i \cdot X = 0[/itex] for [itex]i = 2, \ldots ,m[/itex], and therefore we have found a non-trivial solution to our original system [itex](**)[/itex]. The argument we have just given allows us to proceed stepwise from
one equation to two equations, then from two to three, and so forth.
This concludes the proof.


Homework Equations


The Attempt at a Solution




"We shall subtract a multiple of the first equation from the others to eliminate [itex]x_1[/itex]."

Why do we eliminate [itex]x_1[/itex] here? I mean we do that when solving non-general systems of equations. But here it looks like we could obtain the non-trivial solutions even with [itex](A_2 - A_1) \cdot X = 0[/itex]. Is it because subtracting the first equation from the second without eliminating any variables would just be a random, arbitrary operation?

Also, when solving the general system of equations, why do we eliminate only 1 variable, namely, [itex]x_1[/itex], as opposed to non-general cases where we can usually eliminate more than 1 variable? I can see how eliminating only [itex]x_1[/itex] brings us to the solution in the proof, but is that the only reason?

Thanks.
 
Physics news on Phys.org
  • #2
It's a proof by mathematical induction. That strategy involves (a) showing that a proposition is true when m = 1, and (b) showing that IF the proposition is true for any integer represented as "m - 1" then it will also be true for the successor, m. Together, (a) and (b) imply that the proposition is true for all integers m.

In your problem, the reason why only one unknown is being eliminated is that exactly one equation is also being eliminated: the intent is to subtract a multiple of the 1st equation from EACH of the others, so that one has "m - 1" equations in "n - 1" unknowns. This is the manner of asserting (b) above.

If you're not familiar with mathematical induction, or with Fermat's method of "infinite descent," read about them elsewhere. The style of the proof you presented is more like the Fermat style of proof than the typical inductive proof.
 
  • #3
I am familiar with induction from elementary set theory. This is my first brush with Linear Algebra and this proof is first of its kind I've seen. Like you said it doesn't look very much like a typical induction proof. I am glad you mentioned Fermat's method of "infinite decent". Never heard of it. Will look it up.

I appreciate your explanation of why we eliminate only one variable. Spent the whole day asking everywhere. Didn't get any answers.

I think I see where my confusion stems from. If we subtract one equation from another we are going to have only one equation as a result, not two. I somehow missed this by focusing too much on elimination of $x_1$. So, say, we have 5 equations in 6 unknowns. Removing one unknown by subtraction also removes one equation.

Cool. Thank you.
 

1. What is a linear system of equations with non-trivial solutions?

A linear system of equations with non-trivial solutions is a set of two or more equations that can be solved simultaneously, where the solution is not simply all variables equaling zero. In other words, there is a non-zero solution that satisfies all of the equations in the system.

2. How do you know if a linear system of equations has a non-trivial solution?

A linear system of equations has a non-trivial solution if it has at least one free variable. This means that there is more than one possible solution and the variables cannot all be set to zero.

3. Can a linear system of equations have more than one non-trivial solution?

Yes, a linear system of equations can have infinitely many non-trivial solutions. This occurs when there are multiple free variables in the system, allowing for a variety of combinations that satisfy the equations.

4. How do you solve a linear system of equations with non-trivial solutions?

To solve a linear system of equations with non-trivial solutions, you can use various methods such as elimination, substitution, or matrix operations. The goal is to find the values of the variables that satisfy all of the equations in the system.

5. Why is it important to consider non-trivial solutions in linear systems of equations?

In many real-world applications, there are situations where a system of equations has more than one solution. By considering non-trivial solutions, we can find all possible solutions and determine the most suitable one for a given scenario. Additionally, it allows for a deeper understanding and analysis of the relationships between the variables in the system.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
884
  • Calculus and Beyond Homework Help
Replies
3
Views
495
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
155
  • Calculus and Beyond Homework Help
Replies
1
Views
646
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
767
  • Calculus and Beyond Homework Help
Replies
2
Views
790
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
446
Back
Top