Given an $n \times n$ matrix B, is it always possible to find $n \times n$ matrices A and C, such that ABC "sums" arbitrary entries of B?

Question

For example, let

$$B= \begin{pmatrix} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \\ \end{pmatrix} $$

and let $\oplus$ be a function which sums arbitrary entries of $B$. Consider the new matrix

$$B_\oplus= \begin{pmatrix} \oplus (B) & \oplus (B) & \oplus (B) \\ \oplus (B) & \oplus (B) & \oplus (B) \\ \oplus (B) & \oplus (B) & \oplus (B) \\ \end{pmatrix} $$

where $\oplus (B)$ may take different arguments every time. So the new matrix could look like

$$B= \begin{pmatrix} b_{11}+b_{12} & b_{33} & b_{13} \\ b_{12} & b_{22} & b_{23}+b_{13} \\ b_{31}+ b_{32}& b_{11}+b_{22} & b_{33} \\ \end{pmatrix} $$

Can one always find matrices $A$ and $C$, such that $$ABC=B_\oplus ?$$ (Not just prove that such matrices exist, but actually have a formula or an algorithm which produces such matrices.)

---

A more general variant of the question would be: Given a matrices $B$ and $D$, under which conditions (restrictions on $B$ and $D$) can I find matrices $A$ and $C$, so that $ABC=D$?

Answer 1

The collection of $n\times n$ real matrices, $M_n \stackrel{def}{=} {\mathrm Mat}_{n\times n}(\mathbb{R})$, is a vector space of dimension $n^2$.

Given any $B \in M_n$, there is a $1-1$ correspondence between a way to construct a $B_\oplus$ and linear map from $M_n$ to itself. The collection of ways to build $B_\oplus$ is naturally isomorphic to ${\mathrm Mat}_{n^2}(\mathbb{R})$. Since the later has dimension $n^4$, we need $n^4$ independent parameters to fully specify a way to build $B_\oplus$.

Any matrix expression of the form $ABC$ has at most $2n^2-1$ parameters one can play with. There are $n^2$ parameter from $A$, $n^2$ parameter from $C$ but one need to subtract off one from the overall scaling. It is impossible to use $2n^2-1$ parameter to represent all possible ways to build $B_\oplus$.

Update

To see this is impossible in general even when we limit the coefficients in building $B_\oplus$ to either $0$ or $1$. Consider the case $n = 2$ and $$B = \begin{bmatrix} a & b\\ c & d\end{bmatrix} \quad\text{ and }\quad B_\oplus = \begin{bmatrix} a + d & b\\ c & a + d\end{bmatrix} $$ Assume the existence of $A$, $C$ such that $ABC = B_\oplus$ for all choices of $a,b,c,d$. Taking determinant on both sides, we get

$$\det(AC)(ad-bc) = (a+d)^2 - bc$$ This is a contradiction because LHS doesn't contain terms proportional to $a^2$ while RHS does.

Answer 2

No. Consider a case where $\oplus$ increases the rank of $B$, e.g. if $B$ is the ones matrix (of size bigger than 1x1) and $B_\oplus$ is just B where we replace the top left entry with 2 (easily attainable). In that case, for every $A$ and $C$, $rank(ABC)\leq rank(B)<rank(B_\oplus)$ so $rank(ABC)\neq rank(B_\oplus)$ and thus $ABC\neq B_\oplus$.