How to find out if a transform matrix is separable?
I admit I did not really thought about it before. I hope my notations won't be too sloppy.

I assume that given an operator matrix $A(u,v)$, you can apply this operator as a transform on an image $I$, to obtain an image in a novel domain $J(u,v)$. For instance a Fourier kernel would give $$a_{m,n}(u,v) = \exp^{-2\pi \imath \left(um/M+vn/N\right)}\,.$$

For each choice of a $(u,v)$ pair, you get a specific kernel, for instance a basis element.

The transform is separable, in the common sense, when you can write it as a element-wise product, for instance:
$$a_{m,n}(u,v) = b_{m}(u) . c_{n}(v)  $$
where $b(u)$ and $c(v)$ are 1D  vectors:
$$A(u,v) = b(u) . c^T(v)\,,  $$
one acting on  rows, the other on columns.

Thus, the vectors being of rank at most one (the rank of a matrix is lower than its minimum size), $A$ is at most of rank $1$ as well. I take it as sufficient condition. If I rule out uninteresting matrices and vectors of rank $0$, that should be a necessary condition. More details for instance at A rank-one matrix is the product of two vectors.

So:


if $A$ is of rank $&gt;1$, it does not appear to be separable (at least with this definition)
if $A$ is of rank $1$, take a non-zero vector for the span, and then multiply it by appropriate coordinates to get the matrix back.


For $A_3$, the determinant is zero, so the matrix is rank $1$. You will get vector $[1 -1]^T$ in the image, and quickly:

$$2 A_3 = [1 -1]^T [1 -1]\,.$$

Note, the separation is not unique.