2
$\begingroup$

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?

  • 0
    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?2011-03-26
  • 0
    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.2011-03-26
  • 0
    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?2011-03-26
  • 0
    @Thales: So this is homework?2011-03-26
  • 0
    I was just talking this problem with Solon of Athens last night.2011-03-26
  • 0
    I'm a bit confused. You initially tagged the question as (topology) and now you're speaking about probability. Genericity in the topological (Baire) sense is in general not compatible with the probabilistic one. I can assure you that the answer is **yes** in the topological sense, but I don't about the probabilistic case (I haven't thought about it).2011-03-26
  • 0
    Thank you. Yes it is probably that I am weak for this point. Would you kindly explain a little bit more for this incompatibility? What is the argument in your topological sense?2011-03-26
  • 0
    A *residual* set in $\mathbb{R}^n$ is a set that can't be written as a countable union of nowhere dense sets. Dense residual sets are often called generic. However, there are generic sets of measure zero and there are countable unions of nowhere dense sets that have full measure. The standard example is in a comment to this question: http://math.stackexchange.com/questions/280522011-03-26
  • 0
    It is very good to know. Thank you. Then, what is a topological argument for this problem?2011-03-26
  • 0
    First of all, the set of invertible matrices is open and dense in $\mathbb{R}^{n \times n}$. By the Baire category theorem, open and dense subsets of $\mathbb{R}^{n}$ *are* residual. Using this one can show that the set $(A,b)$ such that $A$ is invertible and $b \notin A(\Delta)$ (where $\Delta$ is the large diagonal, i.e., the set of vectors with at least two equal coordinates) contains an open and dense in $\mathbb{R}^{n\times n} \times \mathbb{R}^{n}$. In that sense the set of equations you're asking about is generic in $\mathbb{R}^{n \times n} \times \mathbb{R}^{n}$.2011-03-26
  • 0
    Yes your example is very instructive. But I am talking about a property of $x$ (elements are distinct), not $b.$2011-03-26
  • 0
    Note that I wrote $b \notin A(\Delta)$. This means there is *no* $x$ 'without distinct elements' such that $Ax = b$.2011-03-26
  • 0
    Thank you. Then how can we show the set of $(A,b)$ contains an open and dense set? It is the essence of this problem and I will appreciate your comments.2011-03-26
  • 0
    Note that I wrote my answer before starting the discussion above, so some comments are obsolete (and I hope not to have offended you).2011-03-26
  • 0
    I now see your answer thank you. So you showed that the set of $(A,b)$ that satisfies the property is open and dense. Make sense. (a). Can it be strengthened to probabilistic sense that we have talked? (b). Now suppose we have a nonlinear system of equations. Can this argument be generalized by linearlizing the system?2011-03-26
  • 0
    Ad (a) I really don't know for sure, but I suspect that in fact *yes*. Ad (b), I'd also say *yes*, but this would be much more messy (you'd need to work in some space $C^k(\mathbb{R}^n, \mathbb{R}^n)$ with the appropriate topology) - see for instance Hirsch, *Differential topology*, Chapter 6. I really feel that both these are different questions and suggest that you open up new threads for that.2011-03-26

1 Answers 1

1

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