Find matrix $A$. How many solutions are there?

Question

The matrices below is matrix multiplcation of $AB=C$ but someone has changed the order of the coloumns in $C$ and erased what was in $A$. What is matrix $A$? Is it the only one? I have no idea how to start. I appreciate all the help I can get.

$$\begin{bmatrix} & & & \\ & & & \\ & & &\\& & & & \end{bmatrix} \cdot\begin{bmatrix}2 & 0 &-1 & -2&-4&-4\\-1 & 1 & 0 & -1&2&-1\\ -4& 0 & 1 & 3&8&5\\ -1&0&0&1&2&1\end{bmatrix}=\begin{bmatrix}1 & 1 &3 & -1&0&2\\0 & 1 & 1 & 0&0&0\\0 & 0 & 0&-1&0& 2\\ 0&0&0&0&1&0\end{bmatrix}$$

Answer 1

There is a unique solution to this problem. The problem states that $AB=C$ holds, but that someone has changed the order of the columns in $C$ and erased what was in $A$. We are told what the matrix $B$ is, but not told what $C$ is. We are only told what $C$ looks like after its columns have been permuted. That is, we are told what $CP$ is for some permutation matrix $P$ which has not been specified.

The reduced row echelon matrix for $B$ (and $C$) plays a role, and I will label it $R$. I will write $L$ and $M$ for the $4\times 4$-matrices for which $LB=R=MC$. (These are uniquely determined, since $B$ and $C$ have rank 4.)

It can be shown that the matrices are:

$$ L = \left[\begin{array}{rrrr} -1&0&-1&1\\ -2&1&-2&3\\ -1&0&0&-2\\ -1&0&-1&2 \end{array}\right],\quad B = \left[\begin{array}{rrrrrr} 2&0&-1&-2&-4&-4\\ -1&1&0&-1&2&-1\\ -4&0&1&3&8&5\\ -1&0&0&1&2&1 \end{array}\right], $$

$$ M = \left[\begin{array}{rrrr} 0&0&-1&0\\ 0&0&0&1\\ 1&-1&-1&0\\ 0&1&0&0 \end{array}\right],\quad C = \left[\begin{array}{rrrrrr} -1&0&1&1&2&3\\ 0&0&0&1&0&1\\ -1&0&0&0&2&0\\ 0&1&0&0&0&0 \end{array}\right], $$

$$ R = LB = MC = \left[\begin{array}{rrrrrr} 1&0&0&0&-2&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&2\\ 0&0&0&1&0&1 \end{array}\right], $$

and $$ A = \left[\begin{array}{rrrr} -1&0&0&-1\\ -1&0&-1&2\\ 1&0&1&-1\\ -2&1&-2&3 \end{array}\right],\quad P = \left[\begin{array}{rrrrrr} 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&1\\ 0&0&1&0&0&0 \end{array}\right]. $$

---

Justification:

We are told that $AB=C$. We are given $B$, but not $A$. We are given a matrix obtained by $C$ by permuting the columns of $C$, that is we are given $CP$ for some $6\times 6$ permutation matrix, but we are not told what $P$ is.

Write $\textrm{Null}(X)$ for the nullspace of matrix $X$. Since $AB=C$, it follows that $ABP=CP$, so $x\in\textrm{Null}(CP)=\textrm{Null}(ABP)$ iff $P^{-1}x\in\textrm{Null}(AB)$. But $B$ and $C$ have rank $4$, so $A$ must be invertible, so $\textrm{Null}(AB)=\textrm{Null}(B)$.

To summarize, $x\in\textrm{Null}(CP)$ iff $P^{-1}x\in \textrm{Null}(B)$. Equivalently, $P\cdot \textrm{Null}(B)=\textrm{Null}(CP)$.

Now we are given the matrices $B$ and $CP$, so we can compute these nullspaces and try to determine which permutation matrices satisfy $P\cdot \textrm{Null}(B) = \textrm{Null}(CP)$. There is only one such matrix, and it is the one I have written above. Here I only sketch the kind of reasoning I used to determine $P$.

Vectors $x\in \textrm{Null}(B)$ must satisfy the following conditions.

1. The second coordinate of $x$ must be $0$.

2. The third coordinate of $x$ must be $+2$ times the fourth coordinate of $x$ and $-2$ times the sixth coordinate of $x$.

3. The first coordinate of $x$ must be $+2$ times the fifth coordinate, but does not have to be $-2$ times another coordinate.

Now vectors in $\textrm{Null}(CP)$ must satisfy the same conditions with different coordinate orders, and comparing the coordinate orders we can determine $P$.

Once $P$ is known, we are basically done. We were given $CP$, so with $P$ we can compute $C$. From $B$ and $C$ we can solve for $A$.

I solved for $A$ by row reducing $[B|I]$ and $[C|I]$ to $[R|L]$ and $[R|M]$ respectively, thereby finding matrices $L$ and $M$ such that $LB=R=MC$. Then $(M^{-1}L)B=C$, forcing $A=M^{-1}L$. This I computed by row reducing $[M|L]$ to $[I|M^{-1}L]$.

I then used Maple to check that $AB$ is indeed a matrix that differs from $CP$ by a permutation of columns.

Answer 2

No solution (In case you don't shuffle $C$)

P.S: Thanks @JeanMarie

Denote the $(i,j)^{th}$ entry of $A$ by $a_{ij}$. $$\begin{bmatrix} a_{11} &a_{12} &a_{13} &a_{14} \\ a_{21} &a_{22} &a_{23} &a_{24} \\ a_{31} &a_{33} &a_{33} &a_{34} \\a_{41} &a_{42} &a_{43} &a_{44} \end{bmatrix} \cdot\begin{bmatrix}2 & 0 &-1 & -2&-4&-4\\-1 & 1 & 0 & -1&2&-1\\ -4& 0 & 1 & 3&8&5\\ -1&0&0&1&2&1\end{bmatrix}=\begin{bmatrix}1 & 1 &3 & -1&0&2\\0 & 1 & 1 & 0&0&0\\0 & 0 & 0&-1&0& 2\\ 0&0&0&0&1&0\end{bmatrix}$$ Multiply the first row of $A$ by the first column of $B$ (inner product), you get $$T = 2a_{11} - a_{21} - 4a_{31} - a_{41} = 1$$ Multiply the first row of $A$ by the fifth column of $B$ (inner product), you get $$-4a_{11} + 2a_{21} + 8a_{31} + 2a_{41} = 0$$ CONTRADICTION!! Since $$-4a_{11} + 2a_{21} + 8a_{31} + 2a_{41} = 0 = -2 (2a_{11} - a_{21} - 4a_{31} - a_{41})= - 2T = -2 = 0 !!$$ Therefore NO SOLUTION

Answer 3

Preliminary: I assume it is clear that equation $AB=C'$ (where $C'$ is a column-shuffled version of $C$) is equivalent to 7 relationships between the 7 columns of $B$ and the corresponding 7 columns of $C'$:

$$A.\begin{pmatrix}2 \\-1\\ -4\\ -1\end{pmatrix}=\begin{pmatrix} . \\ .\\ . \\ . \end{pmatrix}, \ \ A.\begin{pmatrix}0 \\1\\ 0\\ 0\end{pmatrix}=\begin{pmatrix} . \\ .\\ . \\ . \end{pmatrix}, \ \ etc...$$

Here is a solution:

$$A=\pmatrix{-1& 0& 0& -1\\-1& 0& -1& 2\\1& 0& 1& -1\\-2& 1& -2& 3},$$

which is such that

$$\tag{1}\pmatrix{-1& 0& 0& -1\\-1& 0& -1& 2\\1& 0& 1& -1\\-2& 1& -2& 3}\cdot\begin{pmatrix}2 & 0 &-1 & -2&-4&-4\\-1 & 1 & 0 & -1&2&-1\\ -4& 0 & 1 & 3&8&5\\ -1&0&0&1&2&1\end{pmatrix}=\begin{pmatrix}-1 & 0 &1 & 1&2&3\\0 & 0 & 0 & 1& 0 & 1\\ -1& 0 & 0 & 0&2&0\\ 0&1&0&0&0&0\end{pmatrix}$$

One sees that the last matrix is matrix $C$ with its columns shuffled.

The way I have obtained matrix $A$ is in 3 steps:

• a) by observing first that, in matrix $B$ as well as in matrix $C$, there are 2 column vectors (say $U$ and $-2U$ in $B$, and $V$ and $-2V$ in $C$) that are proportional with the same proportionality coefficient, namely columns 1 and 5 in $B$, and columns $4$ and $6$ in $C$. They have to be mapped the ones onto the others.

• b) by reducing, in a second step, matrices $B$ and $C$ to $4 \times 4$ matrices denoted $B_1$, resp. $C_1$ by removing, in each one, the 2 columns that have been found in a). I was looking for linear combinations of columns of $B_1$ and $C_1$ giving $0$ (because neither $B_1$ nor $C_1$ is full rank). As I didn't find something significant, using a CAS, I obtained the kernels (nullspaces) of $B_1$ and $C_1$ : their bases are strikingly similar: $(0,-2,-1,1)$ for $B_1$ and $(-2,-1,1,0)$ for $C_1$; this provides the coefficients of null linear combinations of columns I hadn't found by hand computation. This was an "invitation" to place in correspondence columns numbered 2,3,4 of $B_1$ with columns 1,2,3 of $C_1$.

• c) finally, by creating 2 new $4 \times 4$ matrices $B_2$ and $C_2$ through the following operations : i) removal in $B_1$ and in $C_1$ of one of the columns that has been used by the linear combination $-2,-1,1$, for example column 2 for $B_1$ and column 1 for $C_1$ (these columns being "charged" of the non-invertibility of $B_1$ and $C_1$ !), then ii) "augmenting" $B_2$ and $C_2$ by "concatenation" of $U$ (as defined in part a)) as fourth column for $B_2$ and $V$ for $C_2$. As we must have $A.B_2=C_2$, matrix $A$ is obtained by computing:

$$A=C_2.B_2^{-1}$$

($B_2$ is checked invertible).

As we haven't worked by necessary and sufficient conditions, we have to check (this has been done in (1)) that product $A.B$ gives a shuffled version of $C$.