2
$\begingroup$

What is a quantifier-free formula defining the space of orthostochastic matrices? More precise version below.

Fix $n \in {\Bbb N}$, let ${\mathcal M}_n$ denote the space of real $n\times n$ matrices, and let the space of orthogonal matrices be

$$ {\mathcal O}_n := \left\{ O \in {\mathcal M}_n : \ O^\top = O^{-1} \right\} $$

Consider now the set of orthostochastic matrices, given by

$$ {\mathcal S}_n := \left\{ S \in \mathcal M_n:\ \exists O\in\mathcal O_n \text{ such that } \forall i,j\in\{1,\ldots,n\}, \text{ we have } S_{ij}=O_{ij}^2\right\}.$$

Although the way I have defined this set uses a quantifier ("$\exists$") in addition to field operations, the Tarski-Seidenberg theorem implies there is some quantifier-free way to define the set $\mathcal S_n$ of orthostochastic matrices. Can anybody tell me one?

For $n=1$ or $n=2$, it's easy to name one. For $n=1$, we just have $\mathcal S_n = \{1\}$, so there's nothing to show. For $n=2$, it's a standard fact that $\mathcal S_n$ is the set of bistochastic matrices: letting $e\in\mathbb R^n$ is the vector with every entry being $1$, we have

$$\mathcal S_n= \left\{M\in\mathcal M_n:\ M^\top e = Me=e \text{ and } M_{ij}\geq0 \ \forall i,j\in\{1,\ldots,n\}\right\}$$

But this characterization does not hold for $n>2$.

Is there a known formula that works for arbitrary $n$? Although Tarski-Seidenberg only tells us that such a formula exists for any one $n$, I'd be especially happy to know if there's a formula that "looks the same" in some sense for every $n$.

Improve this question
$\endgroup$
2
  • $\begingroup$ If $A$ and $C$ are meant to be the diagonal entries in what you've written, then I think the identity matrix shows $AC=BD$ doesn't hold in general. But in the very non-representative case of $n=2$, your other conditions do characterize the set. We know that $\mathcal S_2$ is the set of the $2\times2$ matrices with nonnegative entries, rows summing to $1$, and columns summing to 1. But this is not true for $n>2$. $\endgroup$ Commented Mar 23 at 10:19
  • $\begingroup$ A $2\times2$ bistochastic matrix is given by \begin{pmatrix} s & 1 - s \\ 1 - s & s \end{pmatrix} for some $s\in[0,1]$, so you can derive it by squaring entries of the orthogonal matrix $\begin{pmatrix} \sqrt{s} & \sqrt{1-s} \\ -\sqrt{1-s} & \sqrt{s} \end{pmatrix}.$ Here's a characterization of unistochastic matrices (a bigger set than orthostochastic ones) for the $3\times3$ case. In particular, not every bistochastic $3\times3$ matrix is orthostochastic. $\endgroup$ Commented Mar 23 at 19:24

3 Answers 3

Reset to default
1
$\begingroup$

If quantifiers over finite sets depending on $n$ are allowed (cf. the condition $$\forall(i,j)\in[n]^2\ S_{i,j}\ge0 \tag{nonnegativity}\label{pos}$$ in Will Sawin's answer), then the orthostochasticity condition for $S$ can be expressed in a very straightforward way, as follows: $$\eqref{pos}\ \&\ \forall(i,j)\in[n]^2\ \exists\delta_{ij}\in\{-1,1\}\ \\ \text{the matrix $(\delta_{ij}\sqrt{S_{ij}})_{(i,j)\in[n]^2}$ is orthogonal},$$ that is, as $$\eqref{pos}\ \&\ \forall(i,j)\in[n]^2\ \exists\delta_{ij}\in\{-1,1\}\ \\ \forall(k,l)\in[n]^2\ \sum_{j\in[n]}\delta_{kj}\delta_{lj}\sqrt{S_{kj}S_{lj}}=1(k=l),$$ that is, as $$\eqref{pos}\ \&\ \prod_{\delta\in\Delta_n} \sum_{(k,l)\in[n]^2}q_{kl}(\delta,S)=0, \tag{1}\label{1}$$ where $[n]:=\{1,\dots,n\}$, $\Delta_n$ is the set of all $n\times n$ matrices $\delta=(\delta_{ij})_{(i,j)\in[n]^2}$ with entries in the set $\{-1,1\}$, and $$q_{kl}(\delta,S):=\Big(\sum_{j\in[n]}\delta_{kj}\delta_{lj}\sqrt{S_{kj}S_{lj}}-1(k=l)\Big)^2.$$

In \eqref{1}, in addition to sums and products over finite sets (depending on $n$), we only have the quantifier in \eqref{pos}, over the finite set $[n]^2$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is all true (and apparently good enough for the OP!), but it’s a not quantifier-free formula in the sense of the Tarski-Seidenberg theorem: those formulas can have quantifiers over finite sets, but not square roots. $\endgroup$ Commented Mar 24 at 13:22
  • $\begingroup$ @MattF. : The OP asked if "there is some quantifier-free way to define the set $\mathcal S_n$ of orthostochastic matrices", not about "quantifier-free formula in the sense of the Tarski-Seidenberg theorem", even though the OP said that the Tarski-Seidenberg theorem implies such a formula for each given $n$. $\endgroup$ Commented Mar 25 at 13:08
  • $\begingroup$ Previous comment continued: I think what one really needs usually is -- not just a system of polynomial equations and inequalities as given in the conclusion of the Tarski-Seidenberg theorem -- but a more explicit solution of such a system, which is what Mathematica's command Reduce tries to produce, and then one cannot do without square (and other) roots: In[1]:= Reduce[x^2 + y^2 == 1, x, Reals] Out[1]= -1 <= y <= 1 && (x == -Sqrt[1 - y^2] || x == Sqrt[1 - y^2]) $\endgroup$ Commented Mar 25 at 13:08
4
$\begingroup$

A variant of Matt F.'s idea can be used to give a necessary and sufficient condition. (The original idea may also give a necessary and sufficent condition, but I don't know how to prove or refute this.)

A matrix $O$ is orthogonal if and only if $O O^T = I$, or, equivalently, $\operatorname{tr}( M O O^T) = \operatorname{tr}(M)$ for all matrices $M$. We can express $\operatorname{tr}( M O O^T) - \operatorname{tr}(M)$ as a polynomial in the entries $M_{ij}$ of $M$ and the entries $O_{ij}$ of $O$. Now take the product of this polynomial by all other polnomials obtained by reversing the signs of some of the entires of $O$, i.e. substituting in $-O_{ij}$ for some of the variables $O_{ij}$.

The product is now a polynomial in $M_{ij}$ and $O_{ij}$ that is invariant to swapping the signs in $O_{ij}$, and hence a polynomial in $M_{ij}$ and $O_{ij}^2$. Now replace each instance of $O_{ij}^2$ with $S_{ij}$ to obtain a polynomial in $S_{ij}$ and $M_{ij}$.

To get the equations, we set the coefficient of each monomial in the $M_{ij}$, the coefficient being a polynomial in $S_{ij}$, to zero, and also demand all $S_{ij}$ are nonnegative.

This works because the $S_{ij}$ being nonnegative guarantees that each $S_{ij}$ has a real square root $O_{ij}$. The coefficient of each monomial in $M_{ij}$ of our product is zero if and only if the product is identically zero, which happens if and only if some factor of the product is identically zero. Some factor of the product is identically zero if and only if, after swapping the signs of some $O_{ij}$, we have $\operatorname{tr}( M O O^T) - \operatorname{tr}(M)$ for all $M$. But this happens if and only if after swapping the signs of some $O_{ij}$, we obtain an orthogonal matrix, which occurs if and only if $S$ is orthostochastic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. I had polynomial conditions of degree $2^{n-1}$, and you settled the issue with conditions of degree $2^{n^2}$. $\endgroup$ Commented Mar 24 at 23:24
2
$\begingroup$

The conditions for $S_{ij}$ include:

  • for each $i$ and $j$, $S_{ij}\ge 0$;
  • for each $i$, $\sum_j S_{ij}=1$;
  • for each $j\neq k$, the expansion of $$\prod _{\text{all}\pm\text{‘s}}\Big(O_{1j}O_{1k} + \sum_{i>1} \pm O_{ij}O_{ik}\Big)=0$$ with each $O_{ab}^{2m}$ replaced by $S_{ab}^m$;
  • and the corresponding statements about $S^\top$.

These are all translations of statements about $O_{ij}$, and the list may well suffice to constrain the possible $S_{ij}$.

Since the product in the third condition is invariant under $O_{ab}\to -O_{ab}$ for each $a,b$, it is a polynomial with only even-degree terms in each $O_{ab}$, and replacing those even-degree expressions yields a polynomial entirely in terms of the $S_{ab}$.

As an example, if $$\mathcal{O} = \left(\begin{array}\\ p & \,q & r\\ s & \,t & u\\ v & w & x\\ \end{array}\right)\!, \ \ \mathcal{S} = \left(\begin{array}\\ P & \ Q & R\\ S & \ T & U\\ V & W & X\\ \end{array}\right) $$ then one product for the third condition is $$(ps+qt+ru)(ps+qt-ru)(ps-qt+ru)(ps-qt-ru)=0.$$ and the corresponding polynomial condition is $$P^2S^2+Q^2T^2+R^2U^2-2PQST-2PRSU-2QRTU=0.$$ Other conditions might also be needed, but this list already constrains $S$ to the right number of degrees of freedom.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.