Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.