Matrix element value counting in O(1) space

The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.

Given an NxM matrix of integer values, we need to verify that the number of non-zero elements in every row and every column is maximum 2.
The matrix cannot be stored! It comes as a stream (M and N are known in advance but are not constants), row after row, and each element is accessed only once.
The space requirement is O(1), i.e. no additional array of size N or M can be used, only a constant number of variables.

Can this be done?
If not, can it be proved?
Can this be done in O(log(N) + Log(M)) space?

We were taught in undergrad school that if you are unable to provide an adequate solution, prove that no one else can... So I tried to prove to my customer that this can't be done in o(M) space, but was unable to.

Thanks allot

Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements.

Therefore the only interesting part is checking the condition over the columns.
This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c_i \in \{0,1,2\}$ associated with the $i$-th column will be the number of rows seen so far that contain a nonzero element in column $i$. As soon as a row with a nonzero element in column $i$ is seen and $c_i$ was already $2$, you can immediately return "false". If the whole matrix is processed without this happening you can return "true".

Unfortunately, your problem cannot be solved using $x= o(M)$ bits.
Suppose this were the case and consider some matrices with $M$ of columns and $N=2M+1$ rows, of the form described in the following.

The $i$-th of the first $M$ rows will have zeros in all columns $j \neq i$, while $i$-th column will either contain a $0$ or a $1$.

The number of distinct choices for the first $M$ rows is $2^M$, yet there are at most $2^x < 2^M$ (for sufficiently large $M$) different possible states of the $x$ bits of memory. This means that there are (at least) two distinct choices $R$ and $R'$ of the first $M$ rows that leave the algorithm in the same internal state.

In other words, for any choice of the $(M+1)$-th to $(2M+1)$-th rows, the algorithm must behave in the same way, regardless of whether the set of the first $M$ rows was $R$ or $R'$.

Since $R$ and $R'$ are distinct, there must be (at least) one index $i$ such that
the element $r_i$ in the $i$-th column of the $i$-th row of $R$ is different from the element $r'_i$ in the $i$-th column of the $i$-th row of $R'$. Without loss of generality assume that $r_i = 0$ and $r'_i=1$.

For $i=1,\dots,M$, let the $(M+i)$-th row be the row containing a single $1$ in the $i$-th column. Finally, choose the $(2M+1)$-th row to have exactly one $1$ in the $i$-th column.

This leads to a contradiction: On one hand, if the set of the first $M$ rows is $R$, the algorithm must return "true" since there is at most one nonzero element per row and at most two nonzero elements per column; on the other hand, if the set of the first $M$ rows is $R'$, the algorithm must return "false" since column $i$ has $3$ nonzero elements (in the $i$-th, $(M+i)$-th, and $(2M+1)$-th rows).

StackExchange Computer Science Q#116635, answer score: 3