1
$\begingroup$

(This question is a repost of a deleted question I asked, because the previous version had several elements missing)

Setting

For fixed $N \in \mathbb{N}$, I wish to compute the entries of a matrix $P_N$ that is $2^N \times 3^N$-dimensional, real-valued and satisfies:

  1. $P_N^T \textbf{1} = \textbf{1}$

  2. $\textbf{1} P_N^T = \frac{3^N}{2^N} \textbf{1}^T$

where $\textbf{1}$ is the all 1's vector in the appropriate dimension. Additionally, $P_N$ is such that:

(i) its first $2^N$ columns are the first $2^N$ standard basis vectors

(ii) the remaining columns contain 0's in all positions except two, which are unknown entries, $w_{i,j}$, that I need to solve for.

After some analysis, we can conclude that there are (i) $2(3^N - 2^N)$ total variables to solve for, and (ii) $3^N$ equations that they satisfy, which implies that for $N > 3$, the system is "undetermined", so has either no solutions or infinitely many solutions for the $(w_{i,j})_{i,j}$

(In actuality, I know everything about where the non-zero entries of $P$ are, as I know the underlying system of equations it is representing. However, I have not included this, as it may not be necessary to my questions, and more importantly it's really complicated and, as I'm in the middle of formalizing it, the structure is not entirely clear yet either to me).

Question

Are there any computational methods or matrix tricks to show that such a system has a solution, for arbitrary $N$? The reason I ask is because the form of the matrix makes it really tricky to do so explicitly in this case, and so I wonder if there exist other methods to do this (either computational or theoretical), as admittedly I don't have much background in matrix analysis.

I apologize in this question is vague, I wasn't sure and so I can certainly expand if needed, but really just providing me with the most general suggestions is alright too!

Thank you all!

$\endgroup$
1
  • $\begingroup$ @MaxAlekseyev Edited, thanks for the comment. $\endgroup$
    – algebroo
    Aug 25, 2023 at 3:41

2 Answers 2

1
$\begingroup$

There are zero or infinitely many solutions depending on where the non-zero entries have to be. So there is no general-purpose answer.

I don't think your equations are properly stated, as $\boldsymbol 1$ seems to have at least two different meanings. I'll interpret your intention as that every row sums to $3^N/2^N$ and every column sums to $1. If that is incorrect, please let us know.

For a subset $R$ of the rows, let $N(R)$ be the set (not multiset!) of columns $c$ such some entry in column $c$ is allowed to be nonzero for some row in $R$. That is, for some $r\in R$, position $(r,c)$ in the matrix is one of those positions not required to be 0.

Here is a necessary and sufficient condition for there to be a non-negative solution: For every subset $R$ of the rows, $|N(R)| \ge (3/2)^N |R|$.

There is a similar dual nsc with the rows and columns reversed.

Whether this is useful will depend on where your non-zero entries have to be, and without that information little more can be said.

$\endgroup$
2
  • $\begingroup$ Thanks for your response! What do you mean, "some entry in column $c$ is allowed for some row in $R$"? I'm not sure what "allowed" means here exactly. $\endgroup$
    – algebroo
    Aug 25, 2023 at 5:13
  • $\begingroup$ allowed to be nonzero $\endgroup$ Aug 25, 2023 at 8:37
0
$\begingroup$

Essentially the problem asks for a matrix of size $2^N\times C$ such that

  • each column has at most 2 nonzero entries;
  • each column sum equals 1;
  • each row sum equals $\frac{C}{2^N}$.

It is not given but I assume that the matrix entries are also nonnegative. Here $C = 3^N - 2^N$, but I will show that such matrix exists for any $C\geq (N-1)2^N$. It will imply that the original problem is soluble for any $N\geq 1$.

Proof. In the first $2^{N-1}$ columns we put pairs of elements $\{ \frac{C}{2^N}\}$ (here $\{\cdot\}$ denotes the fractional part) and $1-\{ \frac{C}{2^N}\}$ such that they "cover" all rows without overlaps. Then, we focus on the rows covered by elements $1-\{ \frac{C}{2^N}\}$, and in the next $2^{N-2}$ columns cover these rows with pairs $\{ \frac{C}{2^{N-1}}\}$ and $1-\{ \frac{C}{2^{N-1}}\}$, and so on.

So far, we have filled $2^{N-1} + 2^{N-2} + \dots + 2^0 = 2^N - 1$ columns such that each row sum is $\equiv \frac{C}{2^N}\pmod1$ and also $<N\leq \frac{C}{2^N}+1$. It follows that the sum in each row $\leq \frac{C}{2^N}$, and thus in the remaining $2^N\times C-(2^N - 1)$ submatrix the row sums should be integer and nonnegative with the total sum of elements equal $C-(2^N - 1)$. It is easy to see that this matrix can be filled with $0$'s and $1$'s, with a single $1$ in each column, giving a required solution. QED


Here is an example of such a matrix for $N=2$ and $C=3^N-2^N=5$: $$ \begin{bmatrix} \frac14 & 0 & 0 & 1 & 0 \\ 0 & \frac14 & 0 & 0 & 1 \\ \frac34 & 0 & \frac12 & 0 & 0 \\ 0 & \frac34 & \frac12 & 0 & 0 \end{bmatrix} $$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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