Sufficient conditions for non-existence of solution to the system of linear equations

linear algebrasystems of equations

Consider the below system of linear equations

$$\begin{pmatrix}
A & B\\
C & 0
\end{pmatrix}\begin{pmatrix}
x\\y
\end{pmatrix}=0$$

where $A$ is a non-singlular $ n\times n $ square matrix, $B$ is a $n \times m$ matrix, and $C$ is a $p \times n$ matrix with $n>m,p$. Assume that $B$ has full column rank, i.e., all columns of $B$ are independent vectors. I would like to know whether there exists a sufficient condition between two matrices $B$ and $C$ such that the system above does not have non trivial solution.

I have proved that almost all $n\times m$ matrix $B$ give the desired result but I want a exact condition.

Thanks in advance for any comments, suggestions, or answers.

Best Answer

Homogeneous linear systems of equation always have a (trivial) solution, $(x,y) = 0$. However I'm guessing you are referring to the case where the right side can be any vector $(b_1,b_2)$, so I will solve that case.

The matrix equation translates to

$$\begin{cases} Ax + By = b_1\\ Cx = b_2\end{cases}$$

Since $A$ is invertable, $x$ can be expressed from $A, B, y$ and $b_1$ the following way:

$$\begin{align*}Ax+By &= b_1 \\ Ax &= b_1-By \\ A^{-1}Ax &= A^{-1}(b_1-By) \\ x &= A^{-1}(b_1-By)\end{align*}$$

For any input $y$ vector, this will give a solution for $x$, since $A$ is always invertable and you can always multiply it with $b_1-By$. We can use the second condition to find such a $y$, by substituting this formula for $x$:

$$\begin{align*}Cx &= b_2 \\ CA^{-1}(b_1-By) &= b_2 \end{align*}$$

So if we can find a $y$ such that $CA^{-1}(b_1-By) = b_2$, then the original system of equations must have a solution, since if we know $y$, we can always find $x$ through the $x = A^{-1}(b_1-By)$ formula. After expanding the brackets, this is equivalent to the rowspace of $-CA^{-1}B$ containing $b_2+CA^{-1}b_1$, since

\begin{align*}CA^{-1}(b_1-By) &= b_2 \\ CA^{-1}b_1 - CA^{-1}By &= b_2 \\ -CA^{-1}By &= b_2 + CA^{-1}b_1\end{align*}

Answer: So the original system does not have a solution exactly if the rowspace of $-CA^{-1}B$ does not contain $b_2+CA^{-1}By$, or equivalently if $CA^{-1}(b_1-By) = -b_2$ does not have a solution for $y$. If $b_2 = 0$, like in your case, then the system will always have the trivial $(x,y) = (0,0)$ solution.

Answer for the case $b_1 = 0$, $b_2 = 0$, with non-trivial solutions $(x,y) \ne (0,0)$: In this case, we can subsititute $b_1 = 0$ and $b_2 = 0$. The statement that "there is no non-trivial solution" is equivalent to the dimensionality of the rowspace of $−CA^{-1}B$ being $0$, which is further equivalent to the dimensionality of the rowspace of $CA^{-1}B$ being $0$. (I removed the negative sign.) This is true because in this case, the only solution the original system be $(x,y)=(0,0)$.

And, the dimensionality of the rowspace is the rank of the matrix, which yields a very simple equivalent condition:

If $\text{rank}(CA^{−1}B)=0$, then there are no non-trivial solutions to your original problem.