Encoding vectors of size $n$ in matrices which less than $2n$ rows [closed]

Question

I have a set of vectors and each has $n$ nonnegative entries. Moreover, each entry of a vector has a quality: (1) or (2). It makes $2^n$ different possible patterns.

For example, let's take two vectors of size $n=5$ (the numbers inside the brackets indicate the quality of the corresponding entries):

• $x=[1 (1), 2 (1), 1 (2),3 (1), 2 (2)]$, and
• $y=[2 (2), 1 (1), 3 (2),1 (2), 1 (1)]$.

The dot product of such vectors can be defined as follows: only the pairs of entries with the same quality are taken into account. In the example we have: $x^Ty=2.1 + 1.3=5$ since only the second and the third pairs of entries share the same quality.

Now my problem is the following. For each vector, I want to create a matrix containing the different informations (the entries and the qualities). All matrices must have the same number of rows which is the quantity I want to be as small as possible. The number of columns is not important and can be different between matrices. The product of two matrices $X(r\times k_X)$ and $Y(r\times k_Y)$ is defined in the following way: $$\langle X,Y \rangle = \sum_{i=1}^{k_X} \sum_{j=1}^{k_Y} \left(X(:,i)^TY(:,j)\right)^2.$$

By taking the example described above, I can give an easy solution to my problem. If the quality of the entry $x_i$ of a vector is (1), we use $[\sqrt{x_i},0]$ and if it is (2), we use $[0,\sqrt{x_i}]$. The number of rows is then $r=2n$ by defining the following matrices:

$$X=Diag([1,0,\sqrt{2},0,0,1,\sqrt{3},0,0,\sqrt{2}]),$$ $$Y=Diag([0,\sqrt{2},1,0,0,\sqrt{3},0,1,1,0]).$$ It is easy to check that with this trick, only the entries sharing the same quality collide and that the product is $\langle X,Y \rangle = 5$, as expected.

Is there a way to encode the different informations in matrices using less than $2n$ rows such that the product would still be correct in every case? Or is there a way to show it is not possible to do better than $2n$?

In a more general way, do you know if this kind of problem could be related to a particular field?

Thanks!

EDIT:

The first interesting case is when we have two vectors of size $n=2$, e.g. $x=[x_1,x_2]$ and $y=[y_1,y_2]$. For each vector, there are $2^2=4$ possible patterns for the qualities and the corresponding matrices are denoted $X^{(1),(1)}$,$X^{(1),(2)}$,$X^{(2),(1)}$,$X^{(2),(2)}$, and $Y^{(1),(1)}$,$Y^{(1),(2)}$,$Y^{(2),(1)}$,$Y^{(2),(2)}$ respectively.

As explained above, it is easy to find a solution using matrices with $r=2n=4$ rows by defining diagonal matrices. However, is it possible to find matrices with only $r=3$ rows? They must verify:

$$\begin{array}{c|cccc} \langle X,Y\rangle&Y^{(1),(1)}&Y^{(1),(2)}&Y^{(2),(1)}&Y^{(2),(2)}\\ \hline X^{(1),(1)}& x_1y_1+x_2y_2 & x_1y_1 & x_2y_2 & 0 \\ X^{(1),(2)}& x_1y_1 & x_1y_1+x_2y_2 & 0 & x_2y_2 \\ X^{(2),(1)}& x_2y_2 & 0 & x_1y_1+x_2y_2 & x_1y_1 \\ X^{(2),(2)}& 0 &x_2y_2 & x_1y_1 & x_1y_1+x_2y_2 \\ \end{array}$$

An attempt which is only partially correct with $r=3$ is: $$X^{(1),(1)}=\begin{pmatrix}\sqrt{x_1} & 0 \\ 0 & \sqrt{x_2} \\ 0 & 0\end{pmatrix}, X^{(1),(2)}=\begin{pmatrix}\sqrt{x_1} & 0 \\ 0 & 0 \\ 0 & \sqrt{x_2}\end{pmatrix},\\ X^{(2),(1)}=\begin{pmatrix}0 & 0 \\ \sqrt{x_1} & \sqrt{x_2-x_1} \\ 0 & 0\end{pmatrix}, X^{(2),(2)}=\begin{pmatrix}0 & 0 \\ \sqrt{x_1} & 0 \\ 0 & \sqrt{x_2}\end{pmatrix},$$ with which we obtain: $$\begin{array}{c|cccc} \langle X,Y\rangle&Y^{(1),(1)}&Y^{(1),(2)}&Y^{(2),(1)}&Y^{(2),(2)}\\ \hline X^{(1),(1)}& x_1y_1+x_2y_2 & x_1y_1 & x_2y_2 & \color{red}{x_2y_1} \\ X^{(1),(2)}& x_1y_1 & x_1y_1+x_2y_2 & 0 & x_2y_2 \\ X^{(2),(1)}& x_2y_2 & 0 & \color{red}{x_2y_2} & \color{red}{x_2y_1} \\ X^{(2),(2)}& \color{red}{x_1y_2} &x_2y_2 & \color{red}{x_1y_2} & x_1y_1+x_2y_2 \\ \end{array}$$ (the red color indicates an incorrect result).

Answer 1

You cannot have less than $2n$. First of all, notice that after you forget about the unimportant details, you want to calculate $\sum_{i=1}^{2n} a_ib_i$ for some $2n$ pairs of numbers using the matrix product you've described. Then realize that in that matrix product the columns are not needed at all, you can just sum up each column to a single entry, so we want $\sum_{i=1}^{2n} a_ib_i=\sum_{i=1}^{r} v_iw_i$, where the $v_i$'s depend only on the $a_i$'s, and the $b_i$'s depend only on the $w_i$'s. Next, we cheat a little and suppose that each $v_i$ (resp. $w_i$) is a linear combination of the $a_i$'s (resp $b_i$'s) - probably it would lead to some pathological contradiction if this was not the case, but now I don't see a proof. And finally, consider what happens if all but one of the $a_i$'s is zero. This gives $2n$ vectors in $\mathbb R^r$ and if $r<2n$, where is some dependency between them. But that would give a contradiction, if multiplied by the appropriate all but one non-zero $b_i$'s.

Answer 2

If I understand the question, you can do it with one row. Encode quality 1 using nonpositive numbers and quality 2 with nonnegative numbers; the only special case is that you must introduce a negative zero, $-0$ in addition to the usual one. Then the product is $xy = \sum_{i=1}^n {\rm max}(0,x_iy_i)$.