# 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?

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

• why do you want to know? – Will Jagy Jun 12 '16 at 20:57
• @WillJagy For counting stuff. It would – maybe – make the programming easier. Or at least more cool. – Karlo Grba Jun 12 '16 at 20:59
• I think the axiom of choice gives yes as the answer,although actually constructing the matrices might be tricky. I'd imagine they'd have to be variants of the n x n identity matrix designed map the addition. – Mathemagician1234 Jun 12 '16 at 21:01
• reminiscent of math.stackexchange.com/questions/1823520/… Suggest one of those programming contests – Will Jagy Jun 12 '16 at 21:01
• Programming what??? – Will Jagy Jun 12 '16 at 21:02

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.

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

• What can be said about the case where the initial matrix has full rank? – Karlo Grba Jun 13 '16 at 3:24