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

  • $\begingroup$ why do you want to know? $\endgroup$ – Will Jagy Jun 12 '16 at 20:57
  • $\begingroup$ @WillJagy For counting stuff. It would – maybe – make the programming easier. Or at least more cool. $\endgroup$ – Karlo Grba Jun 12 '16 at 20:59
  • $\begingroup$ 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. $\endgroup$ – Mathemagician1234 Jun 12 '16 at 21:01
  • $\begingroup$ reminiscent of math.stackexchange.com/questions/1823520/… Suggest one of those programming contests $\endgroup$ – Will Jagy Jun 12 '16 at 21:01
  • $\begingroup$ Programming what??? $\endgroup$ – 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$.


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

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

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.