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?



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

  • 2
    $\begingroup$ This appears (from the response to my comment on Bob Terell's answer) to be a homework problem. I am downvoting and voting to close pending a more satisfactory response to that comment. $\endgroup$ Apr 25, 2016 at 13:26
  • 2
    $\begingroup$ In view of the OP's evasive responses to further comments on Bob Terrell's answer, I will certainly not be changing my close vote. $\endgroup$ Apr 25, 2016 at 15:27
  • 8
    $\begingroup$ I voted to reopen, since the only objection seems to be a misplaced worry about whether it is homework (rather than, say, about the mathematics itself). If a question is interesting, then answer it; if not, then ignore it. Close questions sparingly, only when it is really off-topic (or offensive, etc.). I don't see any particular problem with interesting homework questions. For a student to engage in mathematics on MO seems like a perfectly valid strategy for learning things. For professors that forbid their students to talk to others about mathematics, I say that it is bad pedagogy. $\endgroup$ Apr 25, 2016 at 18:42
  • 7
    $\begingroup$ I suggest that further discussion about whether the question should be closed or not takes place on the meta post meta.mathoverflow.net/questions/2856/probable-homework $\endgroup$
    – Yemon Choi
    Apr 25, 2016 at 20:24

2 Answers 2


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.

  • $\begingroup$ In your argument, you use the fact that the length of the vectors is $2n$. But the length is $n$. In the question, I presented an easy solution using two entries for each of the $n$ entries of a vector. But this trick does not rule out the possibility to have a better solution when using matrices. And I do not understand, why do you say the columns are not important? $\endgroup$
    – user90628
    Apr 24, 2016 at 21:45
  • $\begingroup$ That is my point, qualities don't matter at all. Since the operations are distributive, you can just treat each entry+property as one coordinate. $\endgroup$
    – domotorp
    Apr 25, 2016 at 10:16

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

  • $\begingroup$ You are using the $max$ operator but I can only use matrices and $\langle X,Y\rangle$ (as defined in the question) as operator. $\endgroup$
    – user90628
    Apr 24, 2016 at 14:49
  • 2
    $\begingroup$ @user90628 : Why can't you use the max operator? $\endgroup$ Apr 25, 2016 at 6:08
  • $\begingroup$ @StevenLandsburg Because in the definition of the problem, I can only define matrices and then compute the product $\langle X,Y \rangle = \sum_{i=1}^{k_X} \sum_{j=1}^{k_Y} \left(X(:,i)^TY(:,j)\right)^2.$. I cannot change the way this product is computed. $\endgroup$
    – user90628
    Apr 25, 2016 at 6:25
  • 6
    $\begingroup$ @user90628 : i don't understand this at all. What defines the problem? Why don't you want to change the way the product is computed? $\endgroup$ Apr 25, 2016 at 13:20
  • 12
    $\begingroup$ @user90628 : I lost you at "It must be done". $\endgroup$ Apr 25, 2016 at 15:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.