Notation: Suppose $\mathbf{A}$ and $\mathbf{B}$ are positive definite matrices in $\mathbb{R}^{n\times n}$ such that $\mathbf{A} \succeq \mathbf{B}$ (Loewner order). Let $\mathcal{S}(n,k)$ be the set of all $k$-subsets of $\{1,2,\dots,n\}$. For any $\mathcal{Q} \subset [n] \triangleq \{1,2,...,n\}$, $\mathbf{M}_\mathcal{Q}$ is the matrix obtained by deleting the rows and columns of matrix $\mathbf{M}$ whose indices are in $\mathcal{Q}$. Similarly, $\mathbf{x}_\mathcal{Q}$ is the vector obtained by deleting the rows of vector $\mathbf{x}$ whose indices are in $\mathcal{Q}$.
Conjecture: For any such $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{x} \in \mathbb{R}^n$ and for all $k \in [n-1]$:
$$ \frac{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{A}_\mathcal{Q} + \mathbf{x}_\mathcal{Q}\mathbf{x}_\mathcal{Q}^\top)}{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{A}_\mathcal{Q})} \leq \frac{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{B}_\mathcal{Q} + \mathbf{x}_\mathcal{Q}\mathbf{x}_\mathcal{Q}^\top)}{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{B}_\mathcal{Q})} \tag{1} $$
Progress so far:
We have $\det(\mathbf{A}_\mathcal{Q}+\mathbf{x}_\mathcal{Q}\mathbf{x}_\mathcal{Q}^\top) = \det(\mathbf{A}_\mathcal{Q})\,(1+\mathbf{x}_\mathcal{Q}^\top \mathbf{A}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q})$. Therefore, (1) can be rewritten as (2): $$ \tag{2} \sum_{\mathcal{Q} \in \mathcal{S}(n,k)}\frac{ \det(\mathbf{A}_\mathcal{Q})\,}{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{A}_\mathcal{Q})} \, \mathbf{x}_\mathcal{Q}^\top \mathbf{A}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q} \leq \sum_{\mathcal{Q} \in \mathcal{S}(n,k)}\frac{ \det(\mathbf{B}_\mathcal{Q})\,}{\sum_{\mathcal{Q} \in \mathcal{S}(n,k)} \det(\mathbf{B}_\mathcal{Q})} \, \mathbf{x}_\mathcal{Q}^\top \mathbf{B}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q} $$
Lemmas: It is easy to show that for any $\mathcal{Q} \subset [n]$:
- (2.1) $\quad \mathbf{A} \succeq \mathbf{B} \Rightarrow \mathbf{A}_\mathcal{Q} \succeq \mathbf{B}_\mathcal{Q}$
- (2.2) $\quad \det(\mathbf{A}_\mathcal{Q}) \geq \det(\mathbf{B}_\mathcal{Q})$
- (2.3) $\quad \mathbf{A}^{-1}_\mathcal{Q} \preceq \mathbf{B}_\mathcal{Q}^{-1} \Rightarrow \mathbf{x}_\mathcal{Q}^\top \mathbf{A}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q} \leq \mathbf{x}_\mathcal{Q}^\top \mathbf{B}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q}$
- (2.4) $\quad \det(\mathbf{A}_\mathcal{Q})\,\mathbf{x}_\mathcal{Q}^\top \mathbf{A}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q} \geq \det(\mathbf{B}_\mathcal{Q})\,\mathbf{x}_\mathcal{Q}^\top \mathbf{B}_\mathcal{Q}^{-1}\mathbf{x}_\mathcal{Q} $
- Through recursion, it suffices to show that (1) or (2) hold for the special case of $\mathbf{A} = \mathbf{B} + \mathbf{p}\mathbf{p}^\top$ for some $\mathbf{p} \in \mathbb{R}^n$.
- A very special case is posted here ($\mathbf{B} = \mathbf{I}$, $\mathbf{A} = \mathbf{I} + \mathbf{p}\mathbf{p}^\top$).
- I haven't encountered any counterexample after running "many" simulations (I know this is not a strong argument).
Update: Let me explain the motivation as requested.
Motivation:
Suppose $\{\mathbf{a}_i\}_{i=1}^{m}$ are some vectors in $\mathbb{R}^n$ ($m \geq n$) and $\mathbf{A}_0 \succ \mathbf{0}$ is a given matrix in $\mathbb{R}^{n \times n}$. Now consider, $$ \begin{align} f_k : 2^{[m]} &\to \mathbb{R}, \\ \mathcal{S} & \mapsto c_k(\mathbf{A}_0 + \sum_{i \in \mathcal{S}}\mathbf{a}_i\mathbf{a}_i^\top) \end{align} $$ where $c_k(\mathbf{A})$ is the coefficient of $x^k$ in the characteristic polynomial of $\mathbf{A}$, i.e., $\det(x\mathbf{I} - \mathbf{A})$.
Conjecture: $f_k$ is monotone log-submodular (multiplicative submodular) for all $k \in \{0,1,\dots,n\}$.
I have proved the monotonicity (maybe for $|f_k|$).
Special Cases: This holds for $k=n-1$ (trace), $k=0$ (determinant is log-submodular) and $k=n$ (constant, $f_n(\mathcal{S}) = 1$).
Now (1) emerges from the proof of log-submodularity (multiplicative submodularity) of $f_k$ after expressing $c_k$ as the sum of determinants of principal minors.
Applications:
I came across this when working on graph Laplacian matrices. $f_k$ for Laplacian matrices (and $\mathbf{a}_i = \mathbf{e}_s - \mathbf{e}_r$ where $\{\mathbf{e}_s\}_{s=1}^n$ is the standard basis) is related to the weighted number of spanning trees. I recently showed that the weighted number of spanning trees is a monotone log-submodular function of the edge set (see a draft here). Other coefficients can be also be nicely related to the weighted number of spanning trees as shown by Alexander Kelmans (as a generalization of Kirchhoff's matrix tree theorem). For Laplacian matrices, (2) has a beautiful interpretation in terms of the expected value of the effective resistance ("distance") between two vertices after performing some random operations on the graph.
(1) and (2) also arise in $k$-DPPs (determinantal point process).