# Solving a Homogeneous System of Equations

1. Jan 30, 2017

### Bashyboy

1. The problem statement, all variables and given/known data
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$.

2. Relevant equations

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

2. Jan 30, 2017

### BvU

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

3. Feb 16, 2017

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

4. Feb 16, 2017

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

5. Feb 16, 2017

### Ray Vickson

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