Solving a Homogeneous System of Equations

• Bashyboy
In summary, the solution to the given homogeneous system of equations for any natural number n is x_i = 0 for all i = 1, 2, ..., n.
Bashyboy

Homework Statement

Let ##n## be some natural number. Solve the following ##n \times n## homogeneous system of equations:

$$\sum_{1|i} x_i = 0$$

$$\sum_{2|i} x_i = 0$$
$$\vdots$$

$$\sum_{n|i} x_i = 0$$,

where ##a|b## means ##b## is divisible by ##a##.

The Attempt at a Solution

After working through examples, it seems that ##x_i = 0## holds for all ##i \in \{1,...,n\}##. Since ##1|i## holds for ##i=1,2,...,n##, the first equation becomes ##\sum_{i=1}^n x_i = 0##. Moreover, since ##n|i## happens if and only if ##i=n##, the last equation reduces to ##x_n = 0##. Through my experiments I noticed that the "second" half of the system equations reduced to a single variable equal to ##0##; i.e., ##x_i = 0## for ##i \in \{n - [\frac{n}{2}],...,n\}##, where ##[a]## denote the greatest integer function.

I tried several times to use these observations in solving the problem, but I didn't have much luck. I could use a hint.

If
Bashyboy said:
the last equation reduces to ##x_n = 0##
you can decrease the size of your system to ##n-1## by removing ##x_n##. And so on. You already did it down to ##n/2##. What stops you from going all the way to ## n = 1## ?

Because I cannot see how the reduction of the "second" half of the system trickles down to the "first" half, thereby reduces it further.

The reduction of the second half seems to leave us with the following system:

$$\sum_{1|i} x_i = 0$$

$$\sum_{2|i} x_i = 0$$

$$\vdots$$

$$\sum_{(n - [n/2] - 1)|i} x_i = 0$$

I realize that I am probably over-complicating this, but I see no way of under-complicating it.

When in doubt do a simple example: n = 10

1 2 3 4 5 6 7 8 9 10 ## \ \ ## from ##\sum_{10|i} x_i = 0##
...
...
1 2 3 4 5 6 7 8 9 10 ## \ \ ## from ##\sum_{6|i} x_i = 0##

Then: ##\sum_{5|i} x_i = 0## says ##x_5 + x_{10} = 0## but we already had ##x_{10} = 0 ## as the first step, so now ##x_5 = 0## and we continue to gnaw at the second half in the same way until we only have 1/4 left, which... etc.

Another way to look at it: you start with n equations in n unknowns. The first step reduces that to n-1 x n-1 and ##x_n = 0 ##, which can now be forgotten about completely.
The second step ##\rightarrow ## n-2 x n-2 ... etc.

Bashyboy said:

Homework Statement

Let ##n## be some natural number. Solve the following ##n \times n## homogeneous system of equations:
$$\sum_{1|i} x_i = 0$$
$$\sum_{2|i} x_i = 0$$
$$\vdots$$
$$\sum_{n|i} x_i = 0$$,
where ##a|b## means ##b## is divisible by ##a##.

You already have it: you have shown that you must have ##x_n = 0##. That means that you can throw out ##x_n## and change ##n## to ##n-1##. In other words, you have a problem with a new, smaller ##n##, and you can just start over. Nothing stops you from continuing like that all the way down to ##n = 1##.

What is a homogeneous system of equations?

A homogeneous system of equations is a set of linear equations where all the variables have a coefficient of 0 in at least one of the equations. This means that all the equations can be written in the form of Ax = 0, where A is a matrix and x is a vector of variables.

What is the difference between a homogeneous and non-homogeneous system of equations?

The main difference is that a non-homogeneous system has at least one equation where the constant term is not equal to 0. This means that the system has a unique solution, while a homogeneous system can have infinite or no solutions.

How can I solve a homogeneous system of equations?

One method is to use the Gauss-Jordan elimination method, where you reduce the system to an upper triangular form and then solve for the variables by back substitution. Another method is to use matrix operations, such as finding the null space of the coefficient matrix, to find the solutions.

Can a homogeneous system of equations have more than one solution?

Yes, a homogeneous system can have infinite solutions if the system is underdetermined, meaning it has more variables than equations. If the system is overdetermined, meaning it has more equations than variables, then it can have no solution or a unique solution.

What is the importance of solving a homogeneous system of equations?

Solving a homogeneous system of equations is important in many fields of science and engineering, such as in solving differential equations, finding equilibrium solutions, and in linear algebra for finding eigenvalues and eigenvectors. It also has applications in computer graphics and coding theory.

• Calculus and Beyond Homework Help
Replies
2
Views
468
• Calculus and Beyond Homework Help
Replies
6
Views
510
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
667
• Calculus and Beyond Homework Help
Replies
6
Views
623
• Calculus and Beyond Homework Help
Replies
3
Views
777
• Calculus and Beyond Homework Help
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus
Replies
5
Views
886
• Calculus and Beyond Homework Help
Replies
7
Views
2K