# Constructive proof that a linear relation between columns implies a linear relation between rows

Let $$M = \left(M_{ij}\right)$$ be a square matrix and let $$v = (v_{i}) \neq 0$$ be such that $$Mv = 0$$. This can be rephrased into requiring that $$\sum_{i} v_{i} M_{i} = 0$$, where $$\{M_{i}\}$$ are the column vectors in $$M$$, i.e. $$(v_{j})$$ gives a linear relation on the columns of $$M$$. I can think of multiple proofs that the existence of $$v$$ implies the existence of a $$w=(w_{j})$$ such that $$M^{t}w = 0$$, but none of them are constructive.

How can we write done the coordinates of such a $$w$$ in terms of the coordinates of $$v$$ and $$M$$? In other words, how can we translate a linear relation of columns into a linear relation of rows?

To be more explicit, I would like a non-trivial expression $$w_j = f(v,M)$$ such that when I compute $$\sum_j w_j M_j$$ (where $$M_j$$ are the row vectors in $$M$$) I obtain $$0$$ by using the fact that $$\sum_{i} v_{i} M_{i} = 0$$. Does such an expression exist?

• $M$ is a square matrix, right?
– user700480
Sep 9, 2021 at 9:58
• The proof that a matrix can be put in RREF is constructive, is it not?
– Pedro
Sep 9, 2021 at 10:48
• $w$ will depend on $M$ as well as $v$, and $w$ can be found from $M$ alone, so I suspect the underlying question is whether $v$ helps in finding $w$ Sep 9, 2021 at 10:52
• @Henry That $w$ depends on $M$ is a good point, I will adjust my question accordingly. Sep 9, 2021 at 11:22
• Whoops, that was a pretty big mistake, $M$ should be square. I have edited accordingly. Sep 9, 2021 at 12:05

## 1 Answer

First of all, you did not rule out the solution $$f(v,M)=0$$, but I'll assume this is not what you had in mind. So I'll assume that $$w:=f(v,M)$$ should satisfy the conditions:

1. $$M^tf(v,M)=0$$
2. $$f(v,M)\neq 0$$ for all $$v,M$$

The answer of course depends on what exactly you mean by an "expression", but what can be said is that if $$M$$ has an odd number of rows, then the function $$f$$ cannot be continuous.

Indeed, assume $$M$$ to have size (2k+1)x(2k+1), and denote the standard basis vectors of $$\mathbb{R}^{2k+1}$$ by $$e_i$$. Assume that there is a continuous function $$f$$ satisfying conditions (1) and (2).

Let $$q\in S^{2k}\subset\mathbb{R}^{2k+1}$$ denote a vector on the unit sphere of dimension $$2k$$, and define the family of matrices $$M(q)=qe_1^t$$. This is a continuous function $$S^{2k}\to End(\mathbb{R}^{2k+1})$$. Now consider $$w(q)=f(e_2, M(q))$$ (this makes sense because $$M(q)e_2=0$$ for all $$q$$). The map $$q\mapsto w(q)$$ satisfies:

• it is a continuous function of $$q$$ (since it is a composition of continuous functions)
• $$q^tw(q)=0$$ for all $$q$$ (Property 1+defn of $$M(q)$$)
• $$w(q)\neq 0$$ for all $$q$$ (Property 2)

By the Hairy Ball Theorem, such a map cannot exist. So either you will have to allow $$f$$ to be discontinuous, or accept that sometimes you will get the trivial answer $$f(v,M)=0$$.

• A previous comment mentioned that putting a matrix in RREF gives a constructive proof that the vector $w$ exists. Your argument implies that, whatever this construction may be, it won't be continuous w.r.t. the entries of $M$. Can this also be understood directly (for example, can it be explained in terms of an arbitrary choice that must be made when putting a matrix in RREF)? Sep 19, 2021 at 13:21
• Well it should not be surprising that the RREF is not a continuous function of the entries. Indeed, $RREF([\epsilon,1])=[1,1/\epsilon]$ and $RREF([0,1])=[0,1]$. Sep 19, 2021 at 15:23