# “Independence” with respect to a particular linear combination?

Suppose $A$ is an $m \times m$ invertible square matrix. $B$ is an $m \times n$ matrix $(m<n)$ with rows $R_1,...,R_m$ which satisfy the following property $P$:

There exist no set of scalars $\lambda_1,...,\lambda_m$, such that $\lambda_i \in \{-1,0,1\} \; \forall i = 1(1)m, \lambda_i \neq 0$ for some $i$, such that $\lambda_1R_1 + ... + \lambda_mR_m = 0$.

Simply put, no row can be expressed as a combination of sums and differences of any subset of the other rows.

$A$ obviously satisfies $P$ since its rows are linearly independent.

My question is, can we say anything about whether $AB$ satisfies $P$ or not? (Something analogous to the property that if $A$ and $B$ have linearly independent rows and are of compatible dimensions then $AB$ has linearly independent rows.)

We can relate the linear independence of row/column vectors to invertible property of matrix.

It's easier if we work with column vectors rather than row vectors.

Proposition 1. If $m \times n$ matrix $\mathbf{B}$ that satisfies property $P$ then so does $\mathbf{AB}$ where $A$ is an $m \times m$ invertible matrix.

Let column vectors in $m \times n$ matrix $\mathbf{B}$ be $\mathbf{b}_i \; (1 \le i \le n)$. Since $\mathbf{B}$ satisfies $P$ so there doesn't exists non-all-zero $x_1, \ldots, x_n \in \{-1,0,1\}$ so $\displaystyle \sum_{i=1}^n x_i \mathbf{b}_i=0$. On the other hand, if we let $\mathbf{x}=(x_i)_{n \times 1}$ then we have $\mathbf{Bx}=\sum_{i=1}^n x_i\mathbf{b}_i$. This follows that there doesn't exists a solution $\mathbf{x}$ for $\mathbf{Bx}=0$ so entries of $\mathbf{x}$ are from $\{-1,0,1\}$ and $\mathbf{x} \ne 0$.

With similar argument, it suffices to prove that there doesn't exist such solution $\mathbf{x}$ to $\mathbf{ABx}=0$. Note that $\mathbf{ABx}=\mathbf{A(Bx)}$ and since $\mathbf{A}$ is invertible, which means only solution for $\mathbf{Ay}=0$ is $\mathbf{y}=0$, we find $\mathbf{Bx}=0$. Combining with the above assumption, we are done.

Change it back to row vectors: If $\mathbf{B}$ satisfies $P$ then so does $\mathbf{BA}$.

We claim that $\mathbf{BA}$ satisfies $P$ if $\mathbf{B}$ satisfies $P$ with $A$ is $n \times n$ invertible matrix.

This time, consider column vectors of $B^T$ and $A^TB^T$ instead. If all row vectors of $B$ satisfy property $P$ then all column vectors of $B^T$ satisfy property $P$, which means all column vectors of $A^TB^T$ satisfy property $P$. And since $A^TB^T=(BA)^T$, we find row vectors in $BA$ satisfies property $P$.

What about row vectors in $\mathbf{AB}$? Does $\mathbf{AB}$ satisfy $P$ if $\mathbf{B}$ does?

This case is different from $\mathbf{BA}$ because we can't apply proposition 1 for this, as $(AB)^T=B^TA^T$, i.e. the invertible matrix is at the right not at the left like in proposition 1. I need to put more thought into this part...

• Er... Is this related to property P? I'm not able to understand. I need to know if AB satisfies property P, given A & B each satisfy property P (detailed above). That was the question. I just pointed out that I'm looking for something analogous to the well-known property that if A & B have linearly independent rows AB has linearly independent rows. – Canine360 Oct 24 '17 at 13:31
• But columns of B are not linearly independent necessarily. They're just not + - combinations of each other. So we can't say Bx=0 => only solution is x=0, can we? – Canine360 Oct 24 '17 at 13:42
• Thanks so much! In the last para when you say "linearly independent" you mean "satisfy property P" right? I have edited accordingly. Pls check. So if I've understood correctly, you've shown that if rows of B satisfy property P (i.e not + - combinations of each other), then so do the rows of AB (i.e. they cannot be + - combinations of each other either). Also if I may add - B satisfying P is a necessary & sufficient condition for AB satisfying P right? – Canine360 Oct 24 '17 at 14:15
• That's right. And I believed the set of $\{-1,0,1\}$ can be replaced by any subset in $\mathbf{R}$. – Tengu Oct 24 '17 at 14:17
• @Canine360 After checking it again, I found that I only proved that row vectors of $\mathbf{BA}$ ($A$ here is $n\times n$) satisfy property $P$ if $\mathbf{B}$ satisfies $P$, but whether $\mathbf{AB}$ satisfies or not remains unknown. – Tengu Oct 24 '17 at 15:05