Solving a Homogeneous System of Equations

[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$.

Homework Equations

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.

 

[BvU]

If

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$ ?

 

[Bashyboy]

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.

 

[BvU]

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.

 

[Ray Vickson]

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$.