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

Question

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?

Answer 1

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