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.

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?

share|improve this question
    
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 1

up vote 1 down vote accepted

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

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.