Let $A$ be a real matrix of size $m\times n$, i.e., $A \in \mathbb{R}^{m\times n}$. Suppose all rows of $A$ are distinct, i.e., $A_i \ne A_j$ for $i\ne j$. Note that $A$ might not be a full rank matrix as it allows $A_i = 2A_j$. I want to find a vector (at least existence) in the column space of $A$ whose entries are all distinct.

I know that if $m \le n$ and $A$ is a full rank matrix, for any vector $b$ whose entries are distinct, we can find a vector $Aw \in Col(A)$ where $w = A^\dagger b$ ($A^\dagger$ is the Moore-Penrose inverse of $A$). However, I am not sure how to prove or disprove this in other cases, i.e., $A$ is not full rank and/or $m > n$.

Any comments/suggestions/answers will be very appreciated.

  • $\begingroup$ Are you considering matrices over the reals? Because for finite fields, it might be possible to construct counter examples simply because there aren't enough distinct elements in the fields for entries in your vector. $\endgroup$ – Dirk Jun 26 at 4:44
  • $\begingroup$ @Dirk Yes, I am considering matrices over the real numbers. $\endgroup$ – induction601 Jun 26 at 4:45

The required vector $x$ always exists.

To begin, as the first two rows of $A$ are different, $a_{1j}\ne a_{2j}$ for some $j$. If we take $x=e_j$, the first two entries of $Ax=a_{\ast j}$ will be distinct.

Now suppose we have found an $x$ such that the first $r\,(\ge2)$ entries of $y=Ax$ are distinct. Suppose $y_{r+1}=y_i$ for some $i\le r$. Pick an index $j$ such that $a_{ij}\ne a_{r+1,j}$. Replace $x$ by $x+te_j$ for a sufficiently small $t>0$. With this new $x$, the first $r+1$ entries of $Ax$ are distinct. Continue in the manner, we will finally obtain a desired vector $x$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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