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.

Let $A\in \Bbb R^{n\times n}$ be a matrix such that $\mathrm{rank}(A) = n-1$ and consider the equation $$ Ax = 0. $$ Clearly, its solutions span a $1$-dimensional space, thus an additional assumption may lead to a unique solution. Let $a\in \mathbb R^n$ be a vector and consider a system of equations $$ \tag{1} \begin{cases} Ax & = 0, \\ a\cdot x & = 0 \end{cases} $$ where $a\cdot x = \sum_i a_ix_i$ is the inner product. I have two questions:

  1. What are necessary and sufficient conditions on $a$ for $(1)$ to have the unique solution?

  2. Can we rewrite $(1)$ in an equivalent matrix form, e.g. $(A+C)x = 0$ for some $C$.

share|improve this question
add comment

4 Answers 4

up vote 3 down vote accepted
  1. The necessary and sufficient condition for $(1)$ to have a unique solution is for $a$ to be linearly independent with the rows of $A$, i.e. for $\operatorname{row}(A)\cup\{a\}$ to span $\mathbb{R}^n$
  2. Since $\operatorname{Rank}(A)=n-1$, there exist $a_1,...,a_n$ such that not all of them are zero and $a_1R^A_1+...+a_nR^A_n=0$ (where $R^A_j$ is the $j$th row of $A$). Fix $i$ such that $a_i\neq0$. Let $C$ be the matrix in which $R^C_i=a$ and $R^C_j=0$ for all $j\neq i$. Check that $(A+C)x=0$ and $(1)$ have precisely the same solutions.
share|improve this answer
    
Those $a_j$ used to find $i$ are different from the entries of the vector $a$ as per $(1)$, isn't it? –  Ilya Jan 3 '13 at 16:33
    
No, not necessarily. Any $a_j$ will do. If $a$ does the job - that's ok. Of course, I did not mean that $a=(a_1,...,a_n)$, if that's what you ask. –  Dennis Gulko Jan 3 '13 at 17:24
add comment

To write the set of equations in an equivalent matrix form, observe that $a^Tx$, where $a$ and $x$ are considered as column vectors, or $1\times n$ matrices, is a $1\times 1$ matrix with entry $a\cdot x$.

Hence, just construct a matrix $B$ whose $n+1$ rows are the $n$ rows of $A$ together with one row equal to $a^T$, and form the equation $Bx = 0$. That's (almost trivially) equivalent to the system you describe.

Doing so should make it clear that your equations are still linear, so in particular if there is any nonzero solution, any scalar multiple of it will still be a solution, and hence non-unique. The zero solution always exists: in order for it to be unique, we need $B$ to have a trivial kernel, which means rank $n$, which means $a^T$ linearly indepdenent from all the other rows.

If you meant for there to be a unique nonzero solution, I would advise a dot-product equation that is not zero. This will correspond to a hyperplane that does not go through the origin, which will meet a line that does go through the origin in at most one place.

share|improve this answer
    
What the dimension of $x$ in your case? –  Ilya Jan 3 '13 at 16:15
    
Still $n$. $B$ is an $n+1\times n$ matrix. –  Ben Millwood Jan 3 '13 at 17:38
add comment

Answer: Define $P=(A^T)(A^T)^{\dagger}$ where $(.)^T$ denotes transpose and $(.)^{\dagger}$ denotes pseudo-inverse. Then $Pa=a$ is a necessary and sufficient condition on $a$ to satisfy your conditions. Note that $P$ is the projection matrix for row-space of $A$.

Explanation: Let $v_1,v_2,...,v_{N-1}$ be an orthogonal basis for rows of $A$ ( only $N-1$ vectors will be there since rank(A)=n-1). Let $v$ be a vector such that $Av=0$. Then $v_1,v_2,...,v_{N-1},v$ (adding $v$ to the basis of rowspace of $A$) will be a orthogonal basis for the whole space. Thus any vector $a$ in the whole space can be decomposed into two parts \begin{align} a=(c_1v_1+c_2v_2+...+c_{N-1}v_{N-1})+cv \end{align} i.e there will be contribution from orthonormal basis of rowspace of $A$ and the single vector $v$. Now, clearly \begin{align} a^Tv=c \end{align} Thus, if you require any vector to have a zero inner-product with $v$, $c=0$, thus that vector should lie completely in the span of row space of A. Thus, when multiplied by the projection matrix of row-space of $A$, we should get back that vector itself.

I just saw the (b) part, please refer to other user's answer for that.

share|improve this answer
add comment

Clearly $x=0$ satisfies both equations. So to be unique we need $x=0$ as the only solution. [Also, if $x\neq 0$ satisfies (1), $kx$ will be another solution.]

The solutions to $Ax=0$ are $x\in Ker A$, which is a 1-dimensional subspace. Taking any $a \in Ker A, a\neq 0$ will thus suffice.

share|improve this answer
    
Your condition on $a$ is sufficient, indeed, but it is not necessary. –  Ben Millwood Jan 3 '13 at 17:39
add comment

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.