\documentclass[11pt]{amsart} \usepackage{amssymb,amsmath,amsthm,mathtools,booktabs,xcolor} \usepackage[margin=1.15in]{geometry} \usepackage{hyperref} \hypersetup{colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black, pdftitle={An explicit determinantal formula for limits of iterative proportional fitting with a binary variable}, pdfauthor={Shankar Sivarajan}} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newcommand{\diag}{\operatorname{diag}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\PP}{\mathbb{P}} \newcommand{\one}{\mathbf{1}} \title[Limits of iterative proportional fitting with a binary variable]{An explicit determinantal formula for limits of iterative proportional fitting with a binary variable} \author{Shankar Sivarajan} \makeatletter \g@addto@macro\@setauthors{% \begin{center}\footnotesize Department of Computational Medicine and Bioinformatics\\ University of Michigan, Ann Arbor, MI, USA\\ \href{mailto:sivarajn@umich.edu}{\texttt{sivarajn@umich.edu}} \end{center}} \makeatother \begin{document} \begin{abstract} Iterative proportional fitting rescales a table cyclically until it has prescribed margins. For a three-way table and its three two-way margins, the limit is in general an algebraic function of the data of degree greater than one, and from the uniform seed table it is the maximum likelihood estimate under the no-three-way-interaction model. We study tables in which one variable is binary, a setting that includes logistic regression of a binary response on two categorical factors and stratified $2\times2$ tables with a common odds ratio. For $2\times2\times K$ tables, we show that the limit is determined by a root of the determinant of an explicit $2^K\times2^K$ matrix, built from one $2\times2$ companion pencil per stratum, and we identify all of its roots. For the uniform seed, this exhibits the unconditional maximum likelihood estimate of the common odds ratio as a root of a polynomial of degree $2^K-1$, and gives an elementary proof that this is the maximum likelihood degree of the model. For $2\times J\times K$ tables and generic data, the fitting equations form a multiparameter eigenvalue problem, which yields a matrix pencil of size $J^{K-1}K^{J-1}$ whose eigenvalues are the values of one cell at all complex solutions. Finally, every complex solution is a fixed point of the iteration; we characterize the real ones that are linearly attracting, and show that for $2\times2\times K$ tables and generic margins only the limit is attracting. \end{abstract} \maketitle \section{Introduction} Iterative proportional fitting adjusts a table to prescribed margins by rescaling it cyclically to match each margin in turn. It was introduced by Deming and Stephan~\cite{DemingStephan}, its convergence was proved in general by Csisz\'ar~\cite{Csiszar}, and it is used wherever a table must be reconciled with known totals, from sample-survey adjustment to the analysis of contingency tables~\cite{Agresti,BFH}. For a three-way table and its three two-way margins, started from a positive seed table $T=(t_{ijk})$, the limit is the unique positive table of the form $P_{ijk}=t_{ijk}a_{ij}b_{ik}c_{jk}$ with the given margins; for the uniform seed $T=\one$ it is the maximum likelihood estimate under the no-three-way-interaction model~\cite{Birch}. Unlike the estimate under the independence model, which is a product of margins, this limit is in general an algebraic function of the data of degree greater than one, and it is computed by the iteration itself. Our aim is to describe it exactly: we show that, when one variable is binary, a coordinate of the limit is a root of an explicit determinant, and we identify the other roots as the remaining complex solutions of the fitting equations. The determinants are a structural description of the limit, not a faster algorithm for computing it. Suppose that one of the three variables is binary. The no-three-way-interaction model for a $2\times J\times K$ table is equivalent to the logistic regression of a binary response on two categorical factors without interaction. For $J=2$ it is the model of homogeneous association for $K$ stratified $2\times2$ tables, as in stratified case--control studies~\cite{MantelHaenszel}, under which the odds ratio is the same in every stratum; the margins $n_{ij+}$, $n_{i+k}$, and $n_{+jk}$ are sufficient, and the common odds ratio $\hat\psi$ of the fitted table is its unconditional maximum likelihood estimate, as distinct from the conditional estimate obtained by conditioning on the stratum margins. For $K=2$, Bartlett~\cite{Bartlett} reduced the fit to a cubic equation (see also~\cite{Teuscher}). Norton~\cite{Norton} gave a scheme of successive approximation for $2\times2\times K$ tables and their generalizations, Roy and Kastenbaum~\cite{RoyKastenbaum} wrote the likelihood equations of an $r\times s\times t$ table as $(r-1)(s-1)(t-1)$ simultaneous equations and solved them numerically, and Birch~\cite{Birch} proved that the likelihood equations have a unique positive solution, at which the likelihood is maximized. For general $K$ the estimate is characterized by the equality of the observed and fitted totals of the cell $(1,1)$, $\sum_kn_{11k}=\sum_k\xi_k(\psi)$, where the fitted value $\xi_k(\psi)$ is the admissible root of a quadratic equation in each stratum, and it is computed iteratively~\cite{BreslowDay}. The Mantel--Haenszel estimator~\cite{MantelHaenszel} is explicit, but it is a different estimator. In algebraic terms, the $2\times J\times K$ model is the Lawrence lifting of the vertex-edge incidence matrix of the complete bipartite graph $K_{J,K}$, the design matrix of the independence model of a $J\times K$ table~\cite{BrysiewiczMaraj}. We show that $\hat\psi$ is a root of an explicit polynomial, given as a single determinant of size $2^K$, and we identify all of its roots (Theorems~\ref{thm:main} and~\ref{thm:mle}). The determinant eliminates the stratum quadratics from the equation $\sum_k\xi_k(\psi)=n_{11+}$: each stratum contributes a quadratic in its own entry $P_{11k}$, with coefficients linear in $\psi$, and the coupling is a Kronecker sum of the companion pencils of these quadratics. For $T=\one$ and $n_{11+}\neq\sum_kn_{1+k}n_{+1k}/n_{++k}$, the determinant is $(\psi-1)^{K2^{K-1}-2^K+1}F(\psi)$, where $F$ has degree $2^K-1$; its roots are the common odds ratios of all complex critical points of the likelihood, and for generic margins they are simple. The number of complex critical points of the likelihood for generic data is the maximum likelihood degree of the model; the value $2^K-1$ was conjectured in~\cite{AmendolaEtAl} and proved in~\cite{BrysiewiczMaraj}, and our argument gives an elementary proof of it together with an explicit polynomial. The estimate $\hat\psi$ is the unique root that belongs to a positive solution (Proposition~\ref{prop:select}). For every positive seed the determinant has degree $K2^{K-1}$, and up to a factor that depends only on the seed, its leading and constant coefficients are products of linear forms in the margins; when the stratum odds ratios of the seed are distinct, this degree is the number of complex solutions for generic margins. For $2\times J\times K$ tables we write the fitted odds as $s_{jk}\alpha_j\beta_k$, where $s_{jk}=t_{1jk}/t_{2jk}$ are the odds of the seed. Each column margin is then a secular equation, one whose terms are rational functions with simple poles, and after inverting the row parameters each margin equation becomes the singularity of a matrix depending linearly on $(1/\alpha_1,\dots,1/\alpha_J,\beta_1,\dots,\beta_K)$: the fit is a multiparameter eigenvalue problem in the sense of Atkinson~\cite{Atkinson}. We prove that for a generic seed table and generic margins the commuting operators of this problem, restricted to an explicit invariant subspace, give a matrix pencil of size $J^{K-1}K^{J-1}$ whose eigenvalues are exactly the values of the cell $(1,1,1)$ at all complex solutions (Theorem~\ref{thm:corner}). For the maximum likelihood case the corresponding pencil is in general singular, and we show that the maximum likelihood eliminant divides the limit of these eliminants along a generic line of seeds $T=\one+\eta T'$ as $\eta\to0$, for generic margins (Theorem~\ref{thm:limit}). We conjecture a description of the remaining eigenvalues of the operators and an exact description of the maximum likelihood eliminant within the singular pencil (Conjectures~\ref{conj:2JK} and~\ref{conj:mle}). For three-way tables of any format, every complex solution is a fixed point of iterative proportional fitting, although from a positive seed the iteration stays positive and reaches only $\hat P$. We compute the derivative of one cycle at each complex solution; at $\hat P$ its spectral radius is the local rate of convergence of the iteration. For a solution $S$ with real entries, the relevant quadratic form is $H_S(z)=\sum_{ijk}S_{ijk}z_{ijk}^2$, the quadratic form of the derivative of the margins with respect to the log-linear parameters, restricted to the tangent space of the model: the solution is linearly attracting if the form is positive definite and linearly unstable if the form is nondegenerate and not positive definite (Theorem~\ref{thm:realfix}), and for generic data one of the two holds. For $2\times2\times K$ tables and generic margins, the fitted table is the only solution with real entries that is linearly attracting (Theorem~\ref{thm:22Kreal}), while complex solutions can be. For matrix and tensor scaling with one-dimensional margins, each entry of the limit is a root of a multilinear resultant that is a single Sylvester determinant~\cite{Sivarajan}. For two-way margins, as here, each entry of the limit is a root of a sparse resultant on the toric variety of the model~\cite{Sivarajan}, for which general formulas are quotients of determinants of Macaulay type~\cite{DAndrea}; the constructions of the present paper use instead the slice structure of the model and the theory of multiparameter eigenvalue problems. \section{Setting}\label{sec:setting} Let $n=(n_{ijk})$ be a positive $2\times J\times K$ table and $T=(t_{ijk})$ a positive seed table of the same format. The model $\mathcal M_T$ consists of the positive tables $P_{ijk}=t_{ijk}a_{ij}b_{ik}c_{jk}$. A table $P\in\mathcal M_T$ with $P_{ij+}=n_{ij+}$, $P_{i+k}=n_{i+k}$, and $P_{+jk}=n_{+jk}$ exists and is unique~\cite[Thms.~2.1, 3.1, Cor.~3.1]{Csiszar} (for $T=\one$ see also~\cite{Birch}), and iterative proportional fitting started at $T$ converges to it~\cite[Thm.~3.2]{Csiszar}; we call it the fitted table $\hat P$. For $T=\one$ it is the maximum likelihood estimate under the no-three-way-interaction model. Write $m_{jk}=n_{+jk}$, $R_j=n_{1j+}$, $C_k=n_{1+k}$, $s_{jk}=t_{1jk}/t_{2jk}$, and $X_{jk}=P_{1jk}$. A positive table with margins $m$ lies in $\mathcal M_T$ exactly when its odds have the form \begin{equation}\label{eq:odds} \frac{X_{jk}}{m_{jk}-X_{jk}}=s_{jk}\,\alpha_j\beta_k, \end{equation} and then it has the prescribed margins exactly when \begin{equation}\label{eq:margins} \sum_kX_{jk}=R_j\quad(1\le j\le J),\qquad\sum_jX_{jk}=C_k\quad(1\le k\le K). \end{equation} The parameters $(\alpha,\beta)$ are determined up to $(\alpha,\beta)\mapsto(\lambda\alpha,\lambda^{-1}\beta)$. A \emph{complex solution} is a pair $(\alpha,\beta)\in(\C^*)^J\times(\C^*)^K$, modulo this scaling, with $1+s_{jk}\alpha_j\beta_k\neq0$ for all $j,k$, such that $X_{jk}=m_{jk}s_{jk}\alpha_j\beta_k/(1+s_{jk}\alpha_j\beta_k)$ satisfies~\eqref{eq:margins}; equivalently, a table $P=T\circ(a_{ij}b_{ik}c_{jk})$ with complex factors and nonzero entries that has the margins of $n$. The fitted table corresponds to the unique positive complex solution. For $T=\one$ the complex solutions are exactly the critical points, with all coordinates nonzero, of the log-likelihood on the model, so for generic data their number is the maximum likelihood degree of the model. By the \emph{eliminant} of a cell, or of a parameter, we mean a polynomial whose roots are its values at the complex solutions; the cell $(1,1,1)$ is the \emph{corner entry}. A property holds for \emph{generic} data if it holds outside a proper Zariski-closed set, that is, for all data outside the zero set of some nonzero polynomial in the entries of $n$ and $T$, or in the margins and $T$, as the context indicates; when $T$ is fixed, the polynomial is in the data that vary. In particular, it holds with probability one for data drawn from any distribution with a density with respect to Lebesgue measure. \section{The common odds ratio of a \texorpdfstring{$2\times2\times K$}{2x2xK} table}\label{sec:22K} Let $J=2$. For each stratum $k$ write \[ r_k=n_{1+k},\qquad r'_k=n_{2+k},\qquad c_k=n_{+1k},\qquad N_k=n_{++k},\qquad \rho_k=\frac{t_{11k}t_{22k}}{t_{12k}t_{21k}}, \] and $N=n_{11+}$; thus $r_k=C_k$ in the notation of Section~\ref{sec:setting}. A table with the prescribed margins of stratum $k$ is determined by $x=P_{11k}$, with entries $x$, $r_k-x$, $c_k-x$, and $r'_k-c_k+x$. By~\eqref{eq:odds}, a positive table with the prescribed stratum margins lies in $\mathcal M_T$ exactly when its stratum odds ratios satisfy \[ \frac{P_{11k}P_{22k}}{P_{12k}P_{21k}}=\psi\rho_k\qquad(1\le k\le K) \] for a common $\psi>0$, namely $\psi=\alpha_1/\alpha_2$; for $T=\one$ it is the common odds ratio. Clearing denominators, $x=P_{11k}$ is a root of \begin{equation}\label{eq:quad} q_k(x;\psi)=u_k(\psi)x^2+v_k(\psi)x+w_k(\psi), \end{equation} \[ u_k=1-\psi\rho_k,\qquad v_k=r'_k-c_k+\psi\rho_k(r_k+c_k),\qquad w_k=-\psi\rho_kr_kc_k, \] and the remaining margins $P_{ij+}$ hold exactly when $\sum_kP_{11k}=N$. Accordingly, a complex solution is a tuple $(\psi,x_1,\dots,x_K)$ with $\psi\neq0$, $q_k(x_k;\psi)=0$ and $x_k(r_k-x_k)(c_k-x_k)(r'_k-c_k+x_k)\neq0$ for every $k$, and $\sum_kx_k=N$. The last condition on the entries is automatic. \begin{lemma}\label{lem:nonzero} If $\psi\neq0$ and $q_k(x;\psi)=0$, then the four entries $x$, $r_k-x$, $c_k-x$, and $r'_k-c_k+x$ are nonzero. \end{lemma} \begin{proof} At the four values of $x$ where an entry vanishes, $q_k(0)=-\psi\rho_kr_kc_k$, $q_k(r_k)=r_kn_{+2k}$, $q_k(c_k)=r'_kc_k$, and $q_k(c_k-r'_k)=-\psi\rho_kr'_kn_{+2k}$, all nonzero. \end{proof} The quadratic~\eqref{eq:quad} is $\det(A_k-xB_k)$ for \[ A_k=\begin{pmatrix}0&-w_k\\1&-v_k\end{pmatrix},\qquad B_k=\begin{pmatrix}1&0\\0&u_k\end{pmatrix}. \] For a $2\times2$ matrix $Y$ and $1\le k\le K$, write $Y^{(k)}=B_1\otimes\dots\otimes B_{k-1}\otimes Y\otimes B_{k+1}\otimes\dots\otimes B_K$, a $2^K\times2^K$ matrix. For $\psi$ with $u_k(\psi)\neq0$ let $x_k^\pm(\psi)$ be the two roots of $q_k(\,\cdot\,;\psi)$, and for $\varepsilon\in\{+,-\}^K$ let $\Sigma^\varepsilon(\psi)=\sum_kx_k^{\varepsilon_k}(\psi)$ be the branch sums, which are branches of an algebraic function of $\psi$. \begin{theorem}\label{thm:main} Define \[ E(\psi)=\det\Bigl(N\,B_1\otimes\dots\otimes B_K-\sum_{k=1}^KA_k^{(k)}\Bigr). \] \begin{enumerate} \item $E$ is a polynomial in $\psi$, and at every $\psi$ with $u_1(\psi)\cdots u_K(\psi)\neq0$, \[ E(\psi)=\prod_{k=1}^Ku_k(\psi)^{2^{K-1}}\prod_{\varepsilon\in\{+,-\}^K}\bigl(N-\Sigma^\varepsilon(\psi)\bigr). \] \item The coefficient of $\psi^{K2^{K-1}}$ in $E$ is \[ \prod_{k=1}^K(-\rho_k)^{2^{K-1}}\prod_{\mathcal A\subseteq\{1,\dots,K\}}\Bigl(N-\sum_{k\in\mathcal A}r_k-\sum_{k\notin\mathcal A}c_k\Bigr), \] and the constant term is $\prod_{\mathcal A}\bigl(N-\sum_{k\in\mathcal A}(c_k-r'_k)\bigr)$. Both are nonzero, so $\deg E=K2^{K-1}$ and $E(0)\neq0$. \item If $\psi_0$ is the parameter of a complex solution and $u_k(\psi_0)\neq0$ for all $k$, then $E(\psi_0)=0$. Conversely, if $E(\psi_0)=0$ with $u_k(\psi_0)\neq0$ for all $k$, then $\psi_0$ is the parameter of a complex solution. If the $\rho_k$ are distinct, the same holds at $\psi_0=1/\rho_k$, where $E(1/\rho_k)=0$ exactly when a complex solution has parameter $1/\rho_k$. \item Suppose the $\rho_k$ are distinct. For generic margins, $E$ has $K2^{K-1}$ simple roots, and there are exactly $K2^{K-1}$ complex solutions, one for each root. \end{enumerate} \end{theorem} \begin{proof} (1) Where $u_k\neq0$ for all $k$, $B=B_1\otimes\dots\otimes B_K$ is invertible and \[ N B-\sum_kA_k^{(k)}=B\Bigl(N-\sum_kI\otimes\dots\otimes B_k^{-1}A_k\otimes\dots\otimes I\Bigr). \] The eigenvalues of $B_k^{-1}A_k$ are the roots $x_k^\pm$ of $\det(A_k-xB_k)=q_k(x)$, the eigenvalues of a Kronecker sum are the sums of eigenvalues, one from each summand, and $\det B=\prod_ku_k^{2^{K-1}}$. The determinant is a polynomial in the entries, which are polynomials in $\psi$. (2) As $\psi\to\infty$, $q_k/(\psi\rho_k)\to-(x-r_k)(x-c_k)$, so $\{x_k^+,x_k^-\}\to\{r_k,c_k\}$, while $u_k^{2^{K-1}}\sim(-\rho_k\psi)^{2^{K-1}}$. Hence $E(\psi)\psi^{-K2^{K-1}}$ tends to the stated product. At $\psi=0$, $u_k=1$ and $q_k=x(x+r'_k-c_k)$, with roots $0$ and $c_k-r'_k$. Since $r_k=n_{11k}+n_{12k}$, $c_k=n_{11k}+n_{21k}$, and $c_k-r'_k=n_{11k}-n_{22k}$, the factors are $-\sum_{k\in\mathcal A}n_{12k}-\sum_{k\notin\mathcal A}n_{21k}<0$ and $\sum_{k\notin\mathcal A}n_{11k}+\sum_{k\in\mathcal A}n_{22k}>0$. (3) If $u_k(\psi_0)\neq0$ for all $k$, the factor $\prod u_k^{2^{K-1}}$ is nonzero and finite, so $E(\psi_0)=0$ exactly when some branch sum equals $N$, that is, when there are roots $x_k$ of $q_k(\,\cdot\,;\psi_0)$ with $\sum_kx_k=N$. Since $E(0)\neq0$, $\psi_0\neq0$, and by Lemma~\ref{lem:nonzero} these roots give a complex solution. At $\psi_0=1/\rho_k$ the quadratic $q_k$ drops degree, $v_k(1/\rho_k)=r_k+r'_k=N_k\neq0$, and $x_k^+$ has a simple pole while $x_k^-\to r_kc_k/N_k$. The $2^{K-1}$ branches with $\varepsilon_k=+$ each contribute a simple pole, which is cancelled by $u_k^{2^{K-1}}$; since the $\rho_k$ are distinct, the other factors are finite. So $E(1/\rho_k)$ is a nonzero constant times $\prod_{\varepsilon_k=-}(N-\Sigma^\varepsilon(1/\rho_k))$, which vanishes exactly when a branch through the finite root $x_k^-(1/\rho_k)$ sums to $N$, that is, when there is a complex solution with parameter $1/\rho_k$. (4) The branch sums through the finite root $x_k^-(1/\rho_k)$ take finitely many values at $\psi=1/\rho_k$, so for all but finitely many $N$ no complex solution has parameter in $\{1/\rho_1,\dots,1/\rho_K\}$, and by (3) $E(1/\rho_k)\neq0$. Apply Lemma~\ref{lem:generic} below with $\Psi=\{1/\rho_1,\dots,1/\rho_K\}$. At every root $\psi_0$ of $E$ exactly one factor $N-\Sigma^\varepsilon$ of the product in (1) vanishes, and it vanishes simply, while the other factors are finite and nonzero; so $\psi_0$ is a simple root of $E$ and carries exactly one complex solution. By (2) there are $K2^{K-1}$ roots, and by (3) every complex solution has one of them as its parameter. \end{proof} \begin{lemma}\label{lem:generic} Fix positive stratum margins $r_k,r'_k,c_k$ and a finite set $\Psi$ of values of $\psi$, and suppose that the $2^K$ numbers $\sum_k(r_k\text{ or }c_k)$ are distinct. For all but finitely many values of $N$, every $\psi_0\notin\Psi$ with $u_1(\psi_0)\cdots u_K(\psi_0)\neq0$ and $N=\Sigma^\varepsilon(\psi_0)$ for some branch $\varepsilon$ is not a branch point of any $x_k^\pm$, lies on exactly one branch, and is a simple zero of $N-\Sigma^\varepsilon$. \end{lemma} \begin{proof} The branch points of the $x_k^\pm$ form a finite set $\Psi_0$, independent of $N$, and the finite values of the branch sums at the points of $\Psi_0$ form a finite set. Each branch sum is nonconstant: it tends to $\sum_k(0\text{ or }c_k-r'_k)$ as $\psi\to0$ and to $\sum_k(r_k\text{ or }c_k)$ as $\psi\to\infty$, and $c_k-r'_k=n_{11k}-n_{22k}<\min(r_k,c_k)$ and $0<\min(r_k,c_k)$, so the second limit exceeds the first. Hence each branch sum has finitely many critical values. Moreover, regard $N$ in Theorem~\ref{thm:main} as an indeterminate, so that $E$ is a polynomial in $\psi$ and $N$ whose roots in $N$ are the branch sums. Its discriminant with respect to $N$ is a polynomial in $\psi$ that does not vanish identically, because as $\psi\to\infty$ the $2^K$ roots in $N$ tend to the distinct limits $\sum_k(r_k\text{ or }c_k)$. Thus two distinct branches agree at only finitely many points $\psi\notin\Psi_0$, giving finitely many further values of $N$. Excluding these finitely many values of $N$ proves the lemma. \end{proof} The set of margins at which the conclusion fails is constructible, being the projection of an algebraic set, and its fiber over each choice of stratum margins satisfying the hypothesis is finite. Since the hypothesis on the numbers $\sum_k(r_k\text{ or }c_k)$ is a polynomial inequality and $N$ can be varied independently of the stratum margins, this set is contained in a proper Zariski-closed set of margins; that is, the conclusion holds for generic margins. \begin{proposition}\label{prop:select} Let $L_k=\max(0,c_k-r'_k)$ and $U_k=\min(r_k,c_k)$. For every $\psi>0$, each $q_k(\,\cdot\,;\psi)$ has exactly one root $\xi_k(\psi)$ in $(L_k,U_k)$, and $\xi_k$ is continuous and strictly increasing, with limits $L_k$ and $U_k$ as $\psi\to0$ and $\psi\to\infty$. There is exactly one $\hat\psi>0$ with $\sum_k\xi_k(\hat\psi)=N$; it is the parameter of the fitted table, $\hat P_{11k}=\xi_k(\hat\psi)$, and $E(\hat\psi)=0$. A null vector of the matrix in Theorem~\ref{thm:main} at $\hat\psi$ is $\bigotimes_k\bigl(-w_k/\xi_k,1\bigr)^{\!\top}$, whose entries are positive. \end{proposition} \begin{proof} On $(L_k,U_k)$ the four entries $x$, $r_k-x$, $c_k-x$, and $r'_k-c_k+x$ are positive, and \[ \frac{d}{dx}\log\frac{x(r'_k-c_k+x)}{(r_k-x)(c_k-x)}=\frac1x+\frac1{r'_k-c_k+x}+\frac1{r_k-x}+\frac1{c_k-x}>0. \] The odds ratio increases from $0$ to $\infty$ on the interval, so it equals $\psi\rho_k$ at exactly one point $\xi_k(\psi)$, which depends continuously and increasingly on $\psi$. The sum $\sum_k\xi_k(\psi)$ therefore increases from $\sum_kL_k$ to $\sum_kU_k$. Since $n$ is positive, $n_{11k}\in(L_k,U_k)$, so $N\in(\sum L_k,\sum U_k)$ and $\hat\psi$ exists and is unique. The table with $P_{11k}=\xi_k(\hat\psi)$ is positive, has the prescribed margins, and has stratum odds ratios $\hat\psi\rho_k$, so it lies in $\mathcal M_T$ and equals $\hat P$. For the null vector, $(A_k-\xi B_k)(y,1)^\top=0$ reads $-\xi y-w_k=0$ and $y-v_k-\xi u_k=0$, and $y=-w_k/\xi=\psi\rho_kr_kc_k/\xi>0$. Writing $y_k$ for these vectors, $A_ky_k=\xi_kB_ky_k$, so $\bigl(NB-\sum_kA_k^{(k)}\bigr)\bigotimes_ky_k=\bigl(N-\sum_k\xi_k\bigr)\bigotimes_kB_ky_k=0$. \end{proof} \subsection*{The maximum likelihood case} For $T=\one$ all $\rho_k$ equal $1$, and the poles in the proof of Theorem~\ref{thm:main}(3) coincide at $\psi=1$. \begin{theorem}\label{thm:mle} Let $T=\one$ and suppose $N\neq\sum_kr_kc_k/N_k$. Then \[ E(\psi)=(\psi-1)^{K2^{K-1}-2^K+1}F(\psi),\qquad\deg F=2^K-1,\qquad F(1)\neq0. \] No complex solution has parameter $1$, and the roots of $F$ are exactly the common odds ratios of the complex solutions; the maximum likelihood estimate $\hat\psi$ is the root of $F$ described in Proposition~\ref{prop:select}. For generic margins, $F$ has $2^K-1$ simple roots and there are exactly $2^K-1$ complex solutions, one for each root. \end{theorem} \begin{proof} Near $\psi=1$, $u_k=1-\psi$ and $v_k\to r'_k+r_k=N_k$, so $x_k^+=-N_k/(1-\psi)+O(1)$ and $x_k^-\to r_kc_k/N_k$. For a branch $\varepsilon$ let $\mathcal A=\{k:\varepsilon_k=+\}$. If $\mathcal A\neq\emptyset$, then $N-\Sigma^\varepsilon=(1-\psi)^{-1}\sum_{k\in\mathcal A}N_k+O(1)$, a simple pole with nonzero residue. The branch $\mathcal A=\emptyset$ tends to $N-\sum_kr_kc_k/N_k\neq0$. The prefactor $(1-\psi)^{K2^{K-1}}$ therefore leaves a zero of order exactly $K2^{K-1}-(2^K-1)$, and $F(1)\neq0$; with Theorem~\ref{thm:main}(2), $\deg F=2^K-1$. At $\psi=1$ each $q_k$ is linear with root $r_kc_k/N_k$, so a complex solution with parameter $1$ would give $N=\sum_kr_kc_k/N_k$. The roots of $F$ are the roots of $E$ other than $1$, at which all $u_k=1-\psi$ are nonzero, so by the first part of Theorem~\ref{thm:main}(3) they are the common odds ratios of the complex solutions. The last statement follows from Lemma~\ref{lem:generic} with $\Psi=\{1\}$, as in the proof of Theorem~\ref{thm:main}(4). \end{proof} The quantity $\sum_kr_kc_k/N_k$ is the expected value of $n_{11+}$ under conditional independence, which appears in the Mantel--Haenszel statistic~\cite{MantelHaenszel}; the hypothesis of Theorem~\ref{thm:mle} excludes exactly the case $\hat\psi=1$. The count $2^K-1$ is the maximum likelihood degree of the model, conjectured in~\cite[Conj.~36]{AmendolaEtAl} and proved in~\cite[Cor.~38]{BrysiewiczMaraj}; Theorem~\ref{thm:mle} gives an elementary proof together with an explicit polynomial. Similarly, Theorem~\ref{thm:main}(4) recovers the number of complex solutions for a generic seed table, which is the degree of the model~\cite[Cor.~8]{AmendolaEtAl}, $K2^{K-1}$~\cite[Prop.~34]{AmendolaEtAl}. The polynomial $F$ can have several real roots, each the common odds ratio of a solution with real entries (Example~\ref{ex:threereal}); among them $\hat\psi$ is singled out by positivity (Proposition~\ref{prop:select}). \section{\texorpdfstring{$2\times J\times K$}{2xJxK} tables}\label{sec:2JK} Return to general $J$, with the notation of Section~\ref{sec:setting}. Set $\theta=(\alpha'_1,\dots,\alpha'_J,\beta_1,\dots,\beta_K)$ with $\alpha'_j=1/\alpha_j$, a point of $\PP^{J+K-1}$, and write $\omega_{jk}=s_{jk}\beta_k/\alpha'_j$, so that $X_{jk}=m_{jk}\omega_{jk}/(1+\omega_{jk})$. Let $\mathbf e_j$ denote the standard basis vectors, $\one$ the all-ones vector, and \[ G_k=-I_J+\tfrac1{C_k}\,m_{\cdot k}\one^\top,\qquad G'_j=-I_K+\tfrac1{R_j}\,m_{j\cdot}\one^\top. \] Define the pencils \begin{align*} W_k(\theta)&=\beta_kG_k-\sum_{j=1}^J\frac{\alpha'_j}{s_{jk}}\mathbf e_j\mathbf e_j^\top\quad\text{on }\C^J\qquad(1\le k\le K),\\ V_j(\theta)&=\sum_{k=1}^K\beta_ks_{jk}\mathbf e_k\mathbf e_k^\top G'_j-\alpha'_jI_K\quad\text{on }\C^K\qquad(1\le j\le J-1). \end{align*} There are $J+K-1$ pencils in $J+K$ homogeneous parameters. \begin{lemma}\label{lem:torus} Let $\theta$ have all coordinates nonzero and $\alpha'_j+s_{jk}\beta_k\neq0$ for all $j,k$. Then all $W_k(\theta)$ and $V_j(\theta)$ are singular if and only if $(\alpha,\beta)$ is a complex solution. The kernels are then spanned by $X_{\cdot k}$ and $X_{j\cdot}$. \end{lemma} \begin{proof} $W_k(\theta)x=0$ reads $x_j(\alpha'_j/s_{jk}+\beta_k)=\beta_km_{jk}(\one^\top x)/C_k$ for all $j$. A nonzero solution has $\one^\top x\neq0$, so up to scaling $x_j=m_{jk}\omega_{jk}/(1+\omega_{jk})$, and $\one^\top x=C_k$ holds exactly when $\sum_jX_{jk}=C_k$. The same computation for $V_j$ gives the row margins for $j0$. Since $S\neq\hat P$, the uniqueness of the positive solution (Proposition~\ref{prop:select}) gives a stratum $k$ with a negative entry. The odds ratio is positive and the margins are positive, so the negative entries of that stratum are exactly $S_{11},S_{22}$ or exactly $S_{12},S_{21}$. In the first case $S_{12}>-S_{11}>0$ and $S_{21}>-S_{22}>0$, because $S_{1+},S_{2+}>0$, so $1/S_{11}+1/S_{12}<0$ and $1/S_{21}+1/S_{22}<0$; the second case is symmetric. Thus $\sum_{ij}1/S_{ij}<0<\prod_{ij}S_{ij}$, and $Q_k<0$. Suppose $\psi<0$, so that $\prod_{ij}S_{ijk}<0$ for every $k$. If $\sum_{ij}1/S_{ijk}>0$ for some $k$, then $Q_k<0$. Otherwise $\sum_{ij}1/S_{ijk}<0$ for every $k$. Let $\tau_k=(\sum_{ij}1/S_{ijk})^{-1}$, $\chi=\bigl(\begin{smallmatrix}1&-1\\-1&1\end{smallmatrix}\bigr)$, and $z_{ijk}=\tau_k\chi_{ij}/S_{ijk}$. In each stratum the interaction contrast $z_{11k}-z_{12k}-z_{21k}+z_{22k}$ equals $1$, so $z_{ijk}-\delta_{(i,j),(1,1)}$ is additive in each stratum, that is, of the form $x^{(k)}_i+y^{(k)}_j$, which lies in $\mathcal L_2+\mathcal L_3$; since $\delta_{(i,j),(1,1)}$ lies in $\mathcal L_1$, $z$ lies in $\mathcal V$. Hence \[ H_S(z)=\sum_k\sum_{ij}S_{ijk}\Bigl(\frac{\tau_k\chi_{ij}}{S_{ijk}}\Bigr)^2=\sum_k\Bigl(\sum_{ij}\frac1{S_{ijk}}\Bigr)^{-1}<0. \] For the genericity statement, note that $\frac{d}{dx}\log$ of the stratum odds ratio at $x=S_{11k}$ is $\sum_{ij}1/S_{ijk}$, so $\sum_{ij}1/S_{ijk}=0$ means that $S_{11k}$ is a double root of $q_k(\,\cdot\,;\psi)$, that is, $\psi$ is a branch point of $x_k^\pm$. For generic margins this does not happen at a complex solution: at parameters with all $u_k\neq0$ by Lemma~\ref{lem:generic}, and at the finitely many $\psi\in\{1/\rho_1,\dots,1/\rho_K\}$ because the branch sums there take finitely many values, so generic $N$ avoids them. The rest follows from Theorem~\ref{thm:realfix}, since for generic margins $H_S$ is nondegenerate. \end{proof} Complex solutions other than $\hat P$ can be linearly attracting (Example~\ref{ex:attract}), so Theorem~\ref{thm:22Kreal} does not extend to them. \appendix \section{Examples}\label{sec:examples} \begin{example}\label{ex:generic} Let $K=3$ and \[ (t_{ij1})=\begin{pmatrix}2&1\\1&5\end{pmatrix},\quad(t_{ij2})=\begin{pmatrix}1&4\\3&1\end{pmatrix},\quad(t_{ij3})=\begin{pmatrix}3&1\\2&2\end{pmatrix}, \] \[ (n_{ij1})=\begin{pmatrix}12&5\\8&10\end{pmatrix},\quad(n_{ij2})=\begin{pmatrix}7&14\\11&6\end{pmatrix},\quad(n_{ij3})=\begin{pmatrix}9&6\\4&13\end{pmatrix}. \] The polynomial $E$ of Theorem~\ref{thm:main} has degree $12$ and is irreducible over $\Q$. Its real roots are $0.1734984020$, $0.1779707973$, $0.9717681410$, $1.2197185992$, $1.9477252408$, and $2.8146073184$, and the root given by Proposition~\ref{prop:select} is $\hat\psi=1.2197185992$. \end{example} \begin{example}\label{ex:mle} With the counts of Example~\ref{ex:generic} and $T=\one$, $E(\psi)$ is a constant multiple of $(\psi-1)^5F(\psi)$, where \begin{multline*} F(\psi)=4236232000\,\psi^7+17421462240\,\psi^6+27735604391\,\psi^5+5810133454\,\psi^4\\ -45268267044\,\psi^3-75784685929\,\psi^2-54554310492\,\psi-16963914240 \end{multline*} is irreducible over $\Q$ and has the single real root $\hat\psi=1.4210239993$, the maximum likelihood estimate of the common odds ratio. \end{example} \begin{example}\label{ex:233generic} Let $J=K=3$, with rows indexed by $j$ and columns by $k$, \[ (t_{1jk})=\begin{pmatrix}3&3&4\\5&1&1\\5&5&2\end{pmatrix},\quad(t_{2jk})=\begin{pmatrix}2&5&3\\2&5&2\\3&4&3\end{pmatrix},\quad (n_{1jk})=\begin{pmatrix}1&1&8\\7&8&5\\8&3&5\end{pmatrix},\quad(n_{2jk})=\begin{pmatrix}8&2&3\\2&5&9\\2&4&4\end{pmatrix}. \] The polynomial $E_{11}$ of Theorem~\ref{thm:corner} has degree $81$ and is irreducible over $\Q$. It has $33$ real roots, of which five lie in the interval $(0,m_{11})=(0,9)$: $2.2887616252$, $2.7354972215$, $3.2838372433$, $4.2591282778$, and $4.5510375640$. The entry of the fitted table is $\hat P_{111}=3.2838372433$. \end{example} \begin{example}\label{ex:233} With the counts of Example~\ref{ex:233generic} and $T=\one$, the polynomial $\mathcal R(x)$ has degree $89$. Its factor $E_{\mathrm{ML}}$ has degree $31$, is irreducible over $\Q$, occurs with multiplicity one, and has the single real root $\hat P_{111}=4.1615312803$. \end{example} \begin{example}\label{ex:234} Let $J=3$, $K=4$, $T=\one$, and \[ (n_{1jk})=\begin{pmatrix}8&3&5&8\\2&3&2&5\\9&2&4&4\end{pmatrix},\qquad(n_{2jk})=\begin{pmatrix}9&2&5&3\\1&7&1&3\\5&5&2&9\end{pmatrix}. \] The polynomial $\mathcal R(x)$ has degree $477$. Its factor $E_{\mathrm{ML}}$ has degree $115$, is irreducible over $\Q$, occurs with multiplicity one, and has the single real root $\hat P_{111}=9.9706390967$. \end{example} \begin{example}\label{ex:attract} Let $K=3$ and \[ (t_{ij1})=\begin{pmatrix}197&53\\98&102\end{pmatrix},\quad(t_{ij2})=\begin{pmatrix}23&5\\23&57\end{pmatrix},\quad(t_{ij3})=\begin{pmatrix}142&79\\85&48\end{pmatrix}, \] \[ (n_{ij1})=\begin{pmatrix}132&430\\663&34\end{pmatrix},\quad(n_{ij2})=\begin{pmatrix}77&439\\472&34\end{pmatrix},\quad(n_{ij3})=\begin{pmatrix}107&518\\785&3493\end{pmatrix}. \] The polynomial $E$ has degree $12$, and $\hat\psi=0.0103229485$. At the pair of complex conjugate solutions with $\psi=-0.0429312847\pm0.0067384684i$, the spectral radius of $D_S$ on $\mathcal V$ is $0.5347$, so these solutions are linearly attracting; at the fitted table it is $0.7310$. \end{example} \begin{example}\label{ex:threereal} Let $K=2$, $T=\one$, and \[ (n_{ij1})=\begin{pmatrix}10&1\\3&1\end{pmatrix},\qquad(n_{ij2})=\begin{pmatrix}1&1\\50&10\end{pmatrix}. \] Then $N=11\neq\sum_kr_kc_k/N_k$, and $E(\psi)$ is a constant multiple of $(\psi-1)F(\psi)$ with \[ F(\psi)=10812\,\psi^3+3686\,\psi^2-5687\,\psi-2420, \] irreducible over $\Q$, with the three real roots $-0.5882641171$, $-0.5054368472$, and $0.7527834652$. Each is the common odds ratio of a complex solution with real entries, and $\hat\psi=0.7527834652$. \end{example} \begin{thebibliography}{99} \bibitem{Agresti} A.~Agresti, \emph{Categorical Data Analysis}, 3rd ed., Wiley Series in Probability and Statistics, John Wiley \& Sons, Hoboken, NJ, 2013. \bibitem{AmendolaEtAl} C.~Am\'endola, N.~Bliss, I.~Burke, C.~R.~Gibbons, M.~Helmer, S.~Ho\c{s}ten, E.~D.~Nash, J.~I.~Rodriguez, and D.~Smolkin, \emph{The maximum likelihood degree of toric varieties}, J.\ Symbolic Comput.\ \textbf{92} (2019), 222--242, \href{https://doi.org/10.1016/j.jsc.2018.04.016}{doi:10.1016/j.jsc.2018.04.016}; numbering as in \href{https://arxiv.org/abs/1703.02251}{arXiv:1703.02251}. \bibitem{Atkinson} F.~V.~Atkinson, \emph{Multiparameter Eigenvalue Problems: Matrices and Compact Operators}, Mathematics in Science and Engineering, vol.~82, Academic Press, New York, 1972. \bibitem{Bartlett} M.~S.~Bartlett, \emph{Contingency table interactions}, Suppl.\ J.\ Roy.\ Statist.\ Soc.\ \textbf{2} (1935), no.~2, 248--252, \href{https://doi.org/10.2307/2983639}{doi:10.2307/2983639}. \bibitem{Birch} M.~W.~Birch, \emph{Maximum likelihood in three-way contingency tables}, J.\ Roy.\ Statist.\ Soc.\ Ser.\ B \textbf{25} (1963), no.~1, 220--233, \href{https://doi.org/10.1111/j.2517-6161.1963.tb00504.x}{doi:10.1111/j.2517-6161.1963.tb00504.x}. \bibitem{BFH} Y.~M.~M.~Bishop, S.~E.~Fienberg, and P.~W.~Holland, \emph{Discrete Multivariate Analysis: Theory and Practice}, MIT Press, Cambridge, MA, 1975; reprinted by Springer, New York, 2007, \href{https://doi.org/10.1007/978-0-387-72806-3}{doi:10.1007/978-0-387-72806-3}. \bibitem{BreslowDay} N.~E.~Breslow and N.~E.~Day, \emph{Statistical Methods in Cancer Research, Vol.~I: The Analysis of Case-Control Studies}, IARC Scientific Publications, no.~32, International Agency for Research on Cancer, Lyon, 1980. \bibitem{BrysiewiczMaraj} T.~Brysiewicz and A.~Maraj, \emph{Lawrence lifts, matroids, and maximum likelihood degrees}, Algebr.\ Stat.\ \textbf{16} (2025), no.~2, 217--242, \href{https://doi.org/10.2140/astat.2025.16.217}{doi:10.2140/astat.2025.16.217}; numbering as in \href{https://arxiv.org/abs/2310.13064}{arXiv:2310.13064}. \bibitem{Csiszar} I.~Csisz\'ar, \emph{$I$-divergence geometry of probability distributions and minimization problems}, Ann.\ Probab.\ \textbf{3} (1975), no.~1, 146--158, \href{https://doi.org/10.1214/aop/1176996454}{doi:10.1214/aop/1176996454}. \bibitem{DAndrea} C.~D'Andrea, \emph{Macaulay style formulas for sparse resultants}, Trans.\ Amer.\ Math.\ Soc.\ \textbf{354} (2002), 2595--2629, \href{https://doi.org/10.1090/S0002-9947-02-02910-0}{doi:10.1090/S0002-9947-02-02910-0}. \bibitem{DemingStephan} W.~E.~Deming and F.~F.~Stephan, \emph{On a least squares adjustment of a sampled frequency table when the expected marginal totals are known}, Ann.\ Math.\ Statist.\ \textbf{11} (1940), no.~4, 427--444, \href{https://doi.org/10.1214/aoms/1177731829}{doi:\allowbreak 10.1214/aoms/1177731829}. \bibitem{Fienberg} S.~E.~Fienberg, \emph{An iterative procedure for estimation in contingency tables}, Ann.\ Math.\ Statist.\ \textbf{41} (1970), no.~3, 907--917, \href{https://doi.org/10.1214/aoms/1177696968}{doi:10.1214/aoms/1177696968}. \bibitem{Hartshorne} R.~Hartshorne, \emph{Algebraic Geometry}, Graduate Texts in Mathematics, vol.~52, Springer, New York, 1977, \href{https://doi.org/10.1007/978-1-4757-3849-0}{doi:10.1007/978-1-4757-3849-0}. \bibitem{HMP} M.~E.~Hochstenbach, C.~Mehl, and B.~Plestenjak, \emph{Solving singular generalized eigenvalue problems by a rank-completing perturbation}, SIAM J.\ Matrix Anal.\ Appl.\ \textbf{40} (2019), no.~3, 1022--1046, \href{https://doi.org/10.1137/18M1188628}{doi:10.1137/18M1188628}; numbering as in \href{https://arxiv.org/abs/1805.07657}{arXiv:1805.07657}. \bibitem{Knight} P.~A.~Knight, \emph{The Sinkhorn--Knopp algorithm: convergence and applications}, SIAM J.\ Matrix Anal.\ Appl.\ \textbf{30} (2008), no.~1, 261--275, \href{https://doi.org/10.1137/060659624}{doi:10.1137/060659624}. \bibitem{Kosir} T.~Ko\v{s}ir, \emph{Finite-dimensional multiparameter spectral theory: the nonderogatory case}, Linear Algebra Appl.\ \textbf{212--213} (1994), 45--70, \href{https://doi.org/10.1016/0024-3795(94)90396-4}{doi:10.1016/0024-3795(94)90396-4}. \bibitem{MantelHaenszel} N.~Mantel and W.~Haenszel, \emph{Statistical aspects of the analysis of data from retrospective studies of disease}, J.\ Natl.\ Cancer Inst.\ \textbf{22} (1959), no.~4, 719--748, \href{https://doi.org/10.1093/jnci/22.4.719}{doi:10.1093/jnci/22.4.719}. \bibitem{Norton} H.~W.~Norton, \emph{Calculation of chi-square for complex contingency tables}, J.\ Amer.\ Statist.\ Assoc.\ \textbf{40} (1945), no.~230, 251--258, \href{https://doi.org/10.2307/2280138}{doi:10.2307/2280138}. \bibitem{RoyKastenbaum} S.~N.~Roy and M.~A.~Kastenbaum, \emph{On the hypothesis of no ``interaction'' in a multi-way contingency table}, Ann.\ Math.\ Statist.\ \textbf{27} (1956), no.~3, 749--757, \href{https://doi.org/10.1214/aoms/1177728181}{doi:10.1214/aoms/1177728181}. \bibitem{Sivarajan} S.~Sivarajan, \emph{An explicit determinantal formula for Sinkhorn limits of matrices and tensors}, \href{https://hexagonmath.org/2611.00433}{hexagon:\allowbreak 2611.00433} (2026). \bibitem{Teuscher} F.~Teuscher, \emph{The quantification of Simpson's paradox and other contributions to contingency table theory}, PLoS ONE \textbf{17} (2022), no.~2, e0262502, \href{https://doi.org/10.1371/journal.pone.0262502}{doi:10.1371/journal.pone.0262502}. \end{thebibliography} \end{document}