Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does not exist.)

How does one find this easily? (So I am asking for an algorithm.)

Edit: all numbers are non-zero integers.

share|improve this question
    
What are $a_1,\ldots,a_n, x_1,\ldots,x_n$? Scalars? Vectors? Are they integral? Real? Complex? Nonnegative? –  user1551 Dec 10 '12 at 13:13

4 Answers 4

up vote 1 down vote accepted

Based on the tags, I'm assuming that the $x_i$ and $a_i$ are supposed to be integers. The procedure below generalizes to the case where you want simultaneous solutions to multiple equations. (It also works the same way if we use any principal ideal domain in place of integers.)

Write the inputs as a $1 \times n$ matrix $X = \begin{pmatrix}x_1 & \dotsb & x_n\end{pmatrix}$; assume $X \ne 0$ or else the problem is trivial. The problem is to find the vectors $A = \begin{pmatrix}a_1 & \dotsb & a_n\end{pmatrix}^T$ such that $XA = 0$. Smith normal form says that we can find an invertible $n \times n$ matrix $T$ such that $XT = \begin{pmatrix}d & 0 & \dotsb & 0\end{pmatrix}$, where $d = \gcd(x_1, \dotsc, x_n)$. (There would also be a $1 \times 1$ matrix $S$ that goes on the left, but we can just take it to be $1$.) Because $X$ only has one row, this is much easier than general Smith normal form: For each $i > 1$, one can perform column operations on $X$ to replace two entries $x_1,x_i$ with $\gcd(x_1,x_i)$ and $0$; for instance, if $\gcd(x,y) = d = px + qy$ and $x = rd$, $y = sd$, then $$ \begin{pmatrix}x & y\end{pmatrix} \begin{pmatrix}p & -s \\ q & r\end{pmatrix} = \begin{pmatrix}d & 0\end{pmatrix} $$ where the matrix is invertible as $pr + qs = (px + qy)/d = 1$.

Now, to solve $XA = 0$ for $A$, we solve $XTB = 0$ for a $n \times 1$ vector $B$, which is easy: any $B$ whose first component is zero will do. Then we just take $A = TB$.

This not only shows that there are always solutions, but that in fact the set of solutions is parametrized by $n-1$ integers.

share|improve this answer

Such $a_i$ do always exist (we can let $a_1 = \cdots = a_n = 0$) for example. The whole set of solutions is a $(n-1)$-dimensional subspace (the whole $k^n$ if $x_1 = \cdots = x_n= 0$) of $k^n$.

share|improve this answer

If you want $a_1x_1+\cdots+a_nx_n = 0$ then you are asking for the vectors $(a_1,\ldots,a_n)$ and $(x_1,\ldots,x_n)$ to be perpendicular, i.e. at right angles to one another. For a fixed $(x_1,\ldots,x_n)$ there is an $(n-1)$-dimensional set of vectors $(a_1,\ldots,a_n)$ for which ${\bf x} \perp {\bf a}.$ To see this, think of a flag pole $(0,0,1)$. The $2$-dimensional ground is made up of all of the vectors perpendicular to the flag pole.

Assume that ${\bf x}$ is non-zero. Then one of the $x_i$ will be non-zero. Let us assume that $x_k \neq 0$ and we want to find $(a_1,\ldots,a_n)$ such that $a_1x_1+\cdots+a_nx_n = 0$, well, clearly:

$$a_k = -\frac{1}{x_k}(a_1x_1+\cdots+a_{k-1}x_{k-1}+a_{k+1}x_{k+1}+\cdots+a_nx_n) \, . $$

Thus, all of the vectors can be generated by choosing arbitrary $(a_1,\ldots,a_{k-1},a_{k+1},\ldots,a_n)$ and putting them into:

$$\left(a_1,\ldots,a_{k-1},-\frac{1}{x_k}(a_1x_1+\cdots+a_{k-1}x_{k-1}+a_{k+1}x_{k+1}+\cdots+a_nx_n),a_{k+1},\ldots,a_n\right) \, . $$

Note that if ${\bf x}$ is zero then all choice of ${\bf a}$ satisfy your equation.

share|improve this answer

You said "all numbers are non-zero integers". I assume that means each $x_i$ is a nonzero integer and you want a solution such that every $a_i$ is a nonzero integer.

If $n=1$, there is no solution.

If $n\ge2$, let $S=x_2+\ldots+x_n$. If $S\not=0$, then $(a_1,a_2,a_3,\,\ldots,\,a_n)=(-S, x_1, x_1, \ldots, x_1)$ is a solution; otherwise, $(-x_2,\, 2x_1,\, x_1, \ldots, x_1)$ is a solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.