# A system of linear equations

Consider a system of linear equations $Ax=b$. Can it be that for a generic choice of $A$ and $b$, elements of $x$ are distinct?

-
Why topology? Also I don't really understand what you mean with "the elements of $x$ are distinct". For example, $x_1=(1,2,3)$ has distinct elements while $x_2=(1,1,1)$ has not? Is this what you mean? –  Giuseppe Negro Mar 26 '11 at 11:34
What is a 'generic choice'? Do you mean for any $A$ and $b$? In that case it's equivalent to just considering all possible $x = Ab$, and by picking $A$ to be $\mathrm{id}$ you can make $x = b$ be any vector. –  Alexei Averchenko Mar 26 '11 at 11:42
Thanks for the comments. (a). Define that elements of $x$ are distinct when: for $x=(x_1,x_2,...,x_n)$, for each $i \ne j$, $x_i \ne x_j.$ (b). Suppose we pick $A$ and $b$ randomly. (For example, elements of $A$ and $b$ are chosen according to independent uniform distribution on $[0,1]$.) Then calculate $x$ when possible. Now, can it be that $x$ has distinct elements in the sense defined in (a) with probability 1? –  Thales Mar 26 '11 at 12:28
@Thales: So this is homework? –  Orbling Mar 26 '11 at 12:37
I was just talking this problem with Solon of Athens last night. –  Thales Mar 26 '11 at 12:50

## 1 Answer

If I understand correctly, you're asking if the set $G$ of pairs $(A,b) \subset \mathbb{R}^{n\times n} \times \mathbb{R}^{n}$ such that the coordinates of a solution $x = (x_1, \ldots, x_{n})$ of $Ax = b$ are necessarily pairwise distinct can be called generic.

If that is indeed the question, the answer is yes and I hope I haven't goofed below.

In fact, $G$ is the open and dense subset of $\mathbb{R}^{n\times n} \times \mathbb{R}^{n}$ consisting of pairs $(A,b)$ such that $\det{A} \neq 0$ and $b \notin A(\Delta)$, where $\Delta = \{x \in \mathbb{R}^{n}\,:\,\exists i\neq j \;\text{such that}\; x_i = x_j\}$ is the large diagonal of $\mathbb{R}^{n}$. If $\det{A} = 0$ there is no solution if $b \neq 0$ and otherwise $x = 0$ is a solution.

To see that $G$ is open, observe that it is the preimage of the open set $\mathbb{R}^{n} \smallsetminus \Delta$ under the continuous map $(A,b) \mapsto A^{-1}b$ defined on the open subset $\operatorname{GL}(n,\mathbb{R}) \times \mathbb{R}^{n}$ of $\mathbb{R}^{n \times n} \times \mathbb{R}^n$. To see that $G$ is dense, let $(A,b) \in \mathbb{R}^{n \times n} \times \mathbb{R}^{n}$ be arbitrary. Choose $A_{k} \in \operatorname{GL}(n,\mathbb{R})$ such that $A_{k} \to A$. Since $\mathbb{R}^{n} \smallsetminus A_{k}(\Delta)$ is open and dense, we know that $B = \bigcap_{k} (\mathbb{R}^{n} \smallsetminus A_{k}(\Delta))$ is dense in $\mathbb{R}^{n}$ by the Baire category theorem, so we may choose $b_{k} \in B$ such that $b_{k} \to b$. Obviously, $(A_k, b_k) \in G$ and $(A_k, b_k) \to (A,b)$.

In other words, "the solution $(x_1, \cdots, x_n)$ of a generic system of $n$ linear equations $Ax = b$ in $n$ variables over $\mathbb{R}$ has pairwise distinct coordinates".

-