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

  • $\begingroup$ 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. $\endgroup$ – Canine360 Oct 24 '17 at 13:31
  • $\begingroup$ 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? $\endgroup$ – Canine360 Oct 24 '17 at 13:42
  • $\begingroup$ 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? $\endgroup$ – Canine360 Oct 24 '17 at 14:15
  • 1
    $\begingroup$ That's right. And I believed the set of $\{-1,0,1\}$ can be replaced by any subset in $\mathbf{R}$. $\endgroup$ – Tengu Oct 24 '17 at 14:17
  • $\begingroup$ @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. $\endgroup$ – Tengu Oct 24 '17 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.