Question

Is it possible to factor an mxn matrix into a product of two matrices mxd and dxn, for every d ?

Answer 1

When \(d=1\) and \(A = \begin{bmatrix} 1&2\\2&4 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&4 \end{bmatrix} = \begin{bmatrix} 1\\2 \end{bmatrix} * \begin{bmatrix} 1&2 \end{bmatrix}\]

Answer 2

When \(d=2\) and \(A = \begin{bmatrix} 1&2\\2&4 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&4 \end{bmatrix}=\begin{bmatrix}1&0\\1&1 \end{bmatrix} * \begin{bmatrix} 1&2 \\1&2\end{bmatrix}\]

Answer 3

When \(d=3\) and \(A = \begin{bmatrix} 1&2\\2&4 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&4 \end{bmatrix}=\begin{bmatrix}1&0&0\\2&-1&-1 \end{bmatrix} * \begin{bmatrix} 1&2 \\1&2\\1&2\end{bmatrix}\]

Answer 4

looks i can keep factoring like that for every \(d\) ?

Answer 5

i think you can too...
i was looking at the row vectors of your second matrix in your factor form it is very repetitive
[1 2] I think this is because the matrix A column vectors are linear dependent
I think I remember the right word there
like column 1 times 2 is column 2 in matrix A
I'm just assuming it wouldn't be as pretty if the columns weren't linear dependent

Answer 6

oh yeah the rows of matrix A are linear dependent too

Answer 7

how did you factor it so fast

Answer 8

Yeah, I took the rows to be dependent so that factoring will be easy

Answer 9

fixed a typo

When \(d=3\) and \(A = \begin{bmatrix} 1&2\\2&4 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&4 \end{bmatrix}=\begin{bmatrix}1&0&0\\2&-1&\color{red}{1} \end{bmatrix} * \begin{bmatrix} 1&2 \\1&2\\1&2\end{bmatrix}\]

Answer 10

I was looking at the row picture while factoring :

first row of AB is obtained by taking linear combinations of the rows of B with the weights set by the first row of A

Answer 11

\[\begin{bmatrix}1&0&0\\2&-1&1 \end{bmatrix} * \begin{bmatrix} 1&2 \\1&2\\1&2\end{bmatrix}\]

To obtain the "second" row of the above product, we take the combinations of rows of the second matrix like this : 2(first row) - 1(second row) + 1(third row)

Answer 12

\[\large 2 [1~~~2] - 1[1~~~2] +1[1~~~2] \]

Answer 13

\[\large [2~~~4] - [1~~~2] +[1~~~2] \]

\[\large [2~~~4] \]

That must be the second row of the product

Answer 14

well i know how to do matrix multiplication
i thought you were just using same fast method to factor matrix A
i guess you were just working backwards

Answer 15

No, I don't have any particular method to factor. Just guessing..
I find multuplying like this way easier than working it element by element

Answer 16

For no reason I feel factoring like this should not be possible for every \(d\)

Answer 17

Let me try an invertible matrix may be

Answer 18

When \(d=2\) and \(A = \begin{bmatrix} 1&2\\2&1 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&5 \end{bmatrix} = \begin{bmatrix} 1&0\\2 &1\end{bmatrix} * \begin{bmatrix} 1&2\\0&1 \end{bmatrix}\]

Answer 19

Definitely, we cannot factor a 2x2 invertible matrix into a product of 2x1 and 1x2 matrices

Answer 20

It seems the minimum value of \(d\) must be rank of the matrix

Answer 21

When \(d=3\) and \(A = \begin{bmatrix} 1&2\\2&5 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&5 \end{bmatrix} = \begin{bmatrix} 1&0&0\\2 &1&0\end{bmatrix} * \begin{bmatrix} 1&2\\0&1 \\\spadesuit & \clubsuit \end{bmatrix}\]

Answer 22

When \(d=4\) and \(A = \begin{bmatrix} 1&2\\2&5 \end{bmatrix}\) :
\[\begin{bmatrix} 1&2\\2&5 \end{bmatrix} = \begin{bmatrix} 1&0&1&1 \\2 &1&1&1\end{bmatrix} * \begin{bmatrix} 1&2\\0&1 \\\spadesuit & \clubsuit \\ -\spadesuit & -\clubsuit \end{bmatrix}\]

Answer 23

guess I'm looking for a proof of this :

when \(d\ge rank(A)\), there exist matrices \(X, Y\) such that

\[\large A_{m\times n} = X_{m\times d}*Y_{d\times n}\]

Answer 24

I noticed that when A is singular and d = 1 then the vectors of the dot product are always in the row space of A ... but the row space of A is only 1 dimension .. so I guess the logic behind it is that you can somehow exploit the fact that the second row of A give no additional information ..

Answer 25

That's a nice observation.

Basically, you're saying that the rows of XY always lie in the row space of Y.

Answer 26

Also, columns of XY always lie in the column space of X.

Answer 27

Yeah . Also when d=1 there is no vector a that if you dot it with a vector b is going to give you an invertible matrix, so if A is invertible to begin with , then a*b can never be A

Answer 28

cause if d=1 a/b will always have dependent collumns/rows

Answer 29

Ahh nice nice
Is it right to say that the rank of XY must be less than the ranks of X and Y ?

Answer 30

I guess yea

Answer 31

would be interesting to have a formal proof , but this is more challenging :D

Answer 32

I think it helps if you think of these as maps and whether or not they can be factored or not.
\[A_{mn} =B_{md}C_{dn}\]
since A maps column vectors from \(\mathbb{R}^n\) to \(\mathbb{R}^m\) (and m to n for row vectors if left multiplied) then in order to not lose information, \(d \ge \min(m,n)\) I think.

Answer 33

Nice, assuming either m or n is the rank of A. if the rank itself is less than m or n, d can be made less right ?

Answer 34

Yeah I guess I was assuming the smaller of m or n was the rank of A, haha whoops