|
6
|
|
|
My solution for $n=3$ (upon Suvrit's request):
To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.
Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu$ the lower bound of $(a_{12},a_{23},a_{31})$, and $\nu$ that of $(a_{21},a_{13},a_{32})$.
Claim: we have $\nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.
Proof of the claim: we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu+\nu\ge0$. Q.E.D.
Adapting this proof to higher $n$ seems difficult, but not impossible.
Let us define
$$s_A(I,J)=\sum_{i\in I,j\in J}a_{ij}.$$
If $A$ is any solution of $A+A^T=M$ and $A{\bf1}={\bf1}$, where $M$ meets the assumptions above, then for every $I,J$, we have
$$s_A(I,J^c)+s_A(J,I^c)=|I|+|J|-s_M(I,J)\ge0.$$
Likewise, $a_{ij}+a_{ji}=m_{ij}\ge0$ for every $i,j$.
We have therefore reduced our question to the following one
Suppose that a matrix $A\in M_n({\mathbb R})$
satisfies $a_{ij}+a_{ji}\ge0$ for every $i,j$, and $s_A(I,J^c)+s_A(J,I^c)\ge0$ for every index sets $I,J$. Is it true that there exists a skew-symmetric matrix $B$, satisfying $B{\bf1}={\bf0}$, such that $A+B$ is entrywise non-negative?
(Remark that for such $B$, one has $s_B(I,J^c)+s_B(J,I^c)\equiv0$.)
A side remark: this set of assumptions about $A$ is redundant. All of them derive from the smaller set of inequalities
$$a_{ij}+a_{ji}\ge0,\quad\forall i,j,\qquad s_A(I,I^c)\ge0,\quad\forall I.$$
As a matter of fact, one has
$$s_A(I,J^c)+s_A(J,I^c)=s_A(I\setminus J,I\setminus J)+s_A(J\setminus I,J\setminus I)+s_A(I\cap J,(I\cap J)^c)+s_A((I\cup J)^c,I\cup J)$$
and $s_A(K,K)\ge0$ follows from $a_{ij}+a_{ji}\ge0$.
|
|
|
|
|
5
|
|
|
Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the set of skew-symmetric matrices $B$ such that but not impossible.Let us define$B{\bf1}=0$) has dimension $s_A(I,J)=\sum_{i\in I,j\in J}a_{ij}.$$If $\frac12(n-1)(n-2)$. At least, the system formed by A$ is any solution of $A+A^T=M$ and $A{\bf1}={\bf1}$ still has a solution. The set of solutions is still of the form A{\bf1}={\bf1}$, where $A+aB$, and its invariants are M$ meets the quantities $a_{ij}+a_{ji}$, assumptions above, then for every $\sum_{j(\ne i)}a_{ij}$ and I,J$, we have$\sum_{i(\ne j)}a_{ij}$. All of them are non-negative$s_A(I,J^c)+s_A(J,I^c)=|I|+|J|-s_M(I,J)\ge0.$$Likewise, being respectively equal $a_{ij}+a_{ji}=m_{ij}\ge0$ for every $i,j$. We have therefore reduced our question to the following one Suppose that a matrix $m_{ij}$, A\in M_n({\mathbb R})$ satisfies $1-\frac{1}{2}m_{ii}$ a_{ij}+a_{ji}\ge0$ for every $i,j$, and $$\sum_{i(\ne j)}m_{ij}+\frac12m_{ii}-1=\frac12\left(\sum_{k,l}m_{kl}-\sum_{k,l(\ne j)}m_{kl}\right)-1\ge\frac12(2n-2(n-1))-1=0.$$The fact s_A(I,J^c)+s_A(J,I^c)\ge0$ for every index sets $I,J$. Is it true that these invariant quantities are non-negative is compatible with the requirement there exists a skew-symmetric matrix $B$, satisfying $B{\bf1}={\bf0}$, such that $A\ge0_n$, but it must not be sufficient, as we did not use all of the A+B$ is entrywise non-negative? (necessary) assumptions.Remark that for such $B$, one has $s_B(I,J^c)+s_B(J,I^c)\equiv0$.)
|
|
|
|
|
4
|
|
|
My solution for $n=3$ (upon Suvrit's request):
To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.
Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu$ the lower bound of $(a_{12},a_{23},a_{31})$, and $\nu$ that of $(a_{21},a_{13},a_{32})$.
Claim: we have $\nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.
Proof of the claim: we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu+\nu\ge0$. Q.E.D.
Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$) has dimension $\frac12(n-1)(n-2)$. At least, the system formed by $A+A^T=M$ and $A{\bf1}={\bf1}$ still has a solution. The set of solutions is still of the form $A+aB$, and its invariants are the quantities $a_{ij}+a_{ji}$, $\sum_{j(\ne i)}a_{ij}$ and $\sum_{i(\ne j)}a_{ij}$. All of them are non-negative, being respectively equal to $m_{ij}$, $1-\frac{1}{2}m_{ii}$ and
$$\sum_{i(\ne j)}m_{ij}+\frac12m_{ii}-1=\frac12\left(\sum_{k,l}m_{kl}-\sum_{k,l(\ne j)}m_{kl}\right)-1\ge\frac12(2n-2(n-1))-1=0.$$
The fact that these invariant quantities are non-negative is compatible with the requirement that $A\ge0_n$, but it must not be sufficient, as we did not use all of the (necessary) assumptions.
|
|
|
|
3
|
|
|
My solution for $n=3$ (upon Suvrit's request):
To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.
Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu$ the lower bound of $(a_{12},a_{23},a_{31})$, and $\nu$ that of $(a_{21},a_{13},a_{32})$.
Claim: we have $\nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.
Proof of the claim: we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu+\nu\ge0$. Q.E.D.
Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$) has dimension $\frac12(n-1)(n-2)$. At least, the system formed by $A+A^T=M$ and $A{\bf1}={\bf1}$ still has a solution. The set of solutions is still of the form $A+aB$, and its invariants are the quantities $a_{ij}+a_{ji}$, $\sum_{j(\ne i)}a_{ij}$ and $\sum_{i(\ne j)}a_{ij}$. All of them are non-negative, being respectively equal to $m_{ij}$, $1-\frac{1}{2}m_{ii}$ and
$$\sum_{i(\ne j)}m_{ij}+\frac12m_{ii}-1=\frac12\left(\sum_{k,l}m_{kl}-\sum_{k,l(\ne j)}m_{kl}\right)-1\ge\frac12(2n-2(n-1))-1=0.$$
|
|
|
|
|
2
|
|
|
My solution for $n=3$ (upon Suvrit's request):
To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.
Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu_-\le\mu_+$ \mu$ the lower and upper bounds bound of $(a_{12},a_{23},a_{31})$, and $\nu_-\le\nu_+$ those for \nu$ that of $(a_{21},a_{13},a_{32})$.
Claim: we have $\mu+\le\mu_-+1$, $\nu_+\le\nu_-+1$, $\mu_++\nu_+\le2$ and $\nu_-+\mu_-\ge0$. These inequalities \nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.
Proof of the claim: let us consider for instance
$$a_{12}-a_{23}=a_{12}+a_{21}-a_{21}-a_{23}=m_{12}+\frac12m_{22}-1\in[-1,1],$$
because $m_{ij}\ge0$ and $2m_{12}+m_{11}+m_{22}\le4$. Similar estimates (of the form $a_{ij}-a_{jk}\in[-1,1]$) prove the two first inequalities. Now the third one; we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu_-+\nu_-\ge0$.
The proof of $\mu_++\nu_+\le2$ is similar. \mu+\nu\ge0$. Q.E.D.
Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$) has dimension $\frac12(n-1)(n-2)$.
|
|
|
|
|
1
|
|
|
My solution for $n=3$ (upon Suvrit's request):
To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.
Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu_-\le\mu_+$ the lower and upper bounds of $(a_{12},a_{23},a_{31})$, and $\nu_-\le\nu_+$ those for $(a_{21},a_{13},a_{32})$.
Claim: we have $\mu+\le\mu_-+1$, $\nu_+\le\nu_-+1$, $\mu_++\nu_+\le2$ and $\nu_-+\mu_-\ge0$. These inequalities allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.
Proof of the claim: let us consider for instance
$$a_{12}-a_{23}=a_{12}+a_{21}-a_{21}-a_{23}=m_{12}+\frac12m_{22}-1\in[-1,1],$$
because $m_{ij}\ge0$ and $2m_{12}+m_{11}+m_{22}\le4$. Similar estimates (of the form $a_{ij}-a_{jk}\in[-1,1]$) prove the two first inequalities. Now the third one; we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu_-+\nu_-\ge0$.
The proof of $\mu_++\nu_+\le2$ is similar. Q.E.D.
Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$) has dimension $\frac12(n-1)(n-2)$.
|
|
|
