1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a Homogeneous System of Equations

  1. Jan 30, 2017 #1
    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. jcsd
  3. Jan 30, 2017 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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## ?
     
  4. Feb 16, 2017 #3
    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.
     
  5. Feb 16, 2017 #4

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Feb 16, 2017 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted