\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts}
\usepackage{amsthm}
\usepackage{thmtools, thm-restate}
\usepackage{mathrsfs}
\usepackage{fullpage}
\usepackage{comment}
\declaretheorem[{style=definition,numberwithin=section}]{definition}
\declaretheorem[{style=definition,sibling=definition}]{theorem}
\declaretheorem[{style=definition,sibling=definition}]{lemma}
\declaretheorem[{style=definition,sibling=definition}]{claim}
\declaretheorem[{style=definition,sibling=definition}]{corollary}
\declaretheorem[{style=definition,sibling=definition}]{conjecture}
\declaretheorem[{style=definition,sibling=definition}]{proposition}
\declaretheorem[{style=definition,sibling=definition}]{observation}
\declaretheorem[{style=definition,sibling=definition}]{fact}
\declaretheorem[{style=plain ,sibling=definition}]{remark}
\declaretheorem[{style=definition,name=Open Question}]{openquestion}
\declaretheorem[{style=definition,name=Goal, sibling=definition}]{goal}
\newcommand{\E}{\mathop{\textrm{E}}}
\newcommand{\gt}{>}
\newcommand{\C}{\mathcal{C}}
\newcommand{\Pt}{\mathcal{P}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\poly}{\textrm{poly}}
\newcommand{\sig}{\textrm{sig}}
\newcommand{\vol}{\mu}
\newcommand{\sd}{\textrm{sd}}
\newcommand{\ac}{\bf{AC^0}}
\newcommand{\eps}{\varepsilon}
\newcommand{\wt}{w}
\newcommand{\Wt}{W}
\newcommand{\dist}{\textrm{dist}}
\newcommand{\orb}{\textrm{Orb}}
\newcommand{\Vars}{\textrm{Vars}}
\newcommand{\df}{\stackrel{\rm def}{=}}
\newcommand{\of}[1]{\left( #1 \right)}
\newcommand{\Var}{\textrm{Var}}
\newcommand{\sgn}{\textrm{sign}}
%\newcommand{\ht}{\textrm{height}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\bigland}{\bigwedge}
\newcommand{\promise}{\textrm{Promise}}
\begin{document}
\title{A technique from Lovasz and Szegedy for showing that matrices related to set-functions are PSD}
\author{Chris Beck}
\maketitle
The goal in this note is to expose in detail a small but very interesting part of a paper of Lovasz \& Szegedy titled ``Limits of Dense Graph Sequences''. In it, they employ a useful factorization of a class of combinatorial matrices which they can use to see that certain matrices are or are not PSD.
\section{M{\"o}bius Inversion}
It is helpful I think to give a linear-algebra oriented definition of M{\"o}bius Inversion to set the stage and fix notation. This part of the exposition is based on chapter 25 in Van Lint \& Wilson's textbook.
Let $P$ denote any finite partially ordered set, and let $\mathbb{F}$ denote any field.
Let $\mathcal{M}_{\mathbb{F}}(P)$ denote the algebra of matrices whose rows and columns are indexed by elements of $P$. (In other words it is the endomoprhism algebra of the vector space $\mathbb{F}^{P}$.)
The \emph{incidence algebra} $\mathbb{A}_{\mathbb{F}} (P)$ is a subalgebra of $\mathcal{M}_{\mathbb{F}}(P)$, consisting of those matrices which have zeros at all positions $(i,j)$ such that $i \not\leq j$.
(We will usually suppress $\mathbb{F}$.)
Alternatively, $\mathbb{A}(P)$ is the subalgebra generated by the elementary matrices $\left\{ e_{i,j} \right\}_{i \leq j}$. It is easy to see that this set of matrices, together with the zero matrix, is closed as a monoid under multiplication, so the linear span of these elements is the whole subalgebra.
An element of $\mathbb{A}(P)$ that is important to our exposition is the \emph{zeta function} of $P$, defined by
\[ \zeta(x,y) = \left\{ \begin{array}{lc} 1 & \textrm{ if } x \leq y \textrm{ in } P \\ 0 & \textrm{otherwise} \end{array} \right. \ .\]
$\zeta$ corresponds to the matrix $Z$ in Lovasz \& Szegedy's paper.
Because $\zeta$ has ones along the diagonal and is upper triangular otherwise (with respect to any total ordering extending $P$), $\zeta$ has an inverse in $\mathbb{A}(P)$, and the inverse matrix corresponds to the M{\"o}bius function of $P$.
Then (as is well known) the traditional statement of M{\"o}bius inversion can be stated linear algebraically: Suppose that $f, g$ are two vectors in $\mathbb{F}^{P}$, such that $f = \zeta g$ as matrices. Then $\mu f = g$.
The more traditional formulation (which we will use below) is the following:
\begin{theorem}
Let $f : P \to A$ be any function from $P$ to an abelian group $A$.
Let $g$ be the function defined by
\[ g(x) := \sum_{x \leq y} f(y) \ ,\]
Then, it also holds that
\[ f(x) = \sum_{x \leq y} \mu(x,y) g(y) \ .\]
\end{theorem}
\begin{proof}
If $f,g$ are treated as column vectors, the assumption is equivalent to $g = \zeta f$, and the conclusion can be similarly seen to be equivalent to $f = \mu g$. To be completely formal and allow them to take values in an arbitrary abelian group (as the principle is traditionally stated), we should work over a $\mathbb{Z}$-module rather than a vector space over $\mathbb{F}$, which is sufficient to construct the incidence algebra, and build $\zeta$ and $\mu$. Since any abelian group is a $\mathbb{Z}$-module trivially, this proves the traditional formulation. It is possible to prove by an explicit inductive construction that the inverse of $\zeta$ exists uniquely, so we can get $\mu$ without appealing to linear algebra. We'll omit this here.
\end{proof}
\section{An application for PSD matrices}
The following is implicit in Lovasz \& Szegedy. They call this the ``Lindstrom-Wilf formula'', although they don't cite any particular source for this and I didn't find any reference for this formula online.
\begin{lemma}
(Lovasz \& Szegedy)
Let $P$ be a finite lattice.
Let $f$ denote any function $f : P \to \mathbb{R}$, and let $f'$ denote the M{\"o}bius inverse $\mu f$.
Let $\alpha$ denote the matrix defined by $\alpha(S, T) := f(S \cup T)$. Then $\alpha$ is PSD if and only if $f'$ is everywhere nonnegative.
\end{lemma}
\begin{proof}
Let $D$ denote the diagonal matrix defined by
\[ D_{x,y} := \left\{ \begin{array}{lc} f'(x) & x = y \\ 0 & \textrm{otherwise} \end{array} \right. \ .\]
The lemma follows from the claim:
\begin{claim}
$\alpha$ can be factorized as \[ \alpha = \zeta D \zeta^{T} \ .\]
\end{claim}
Note that, since $\zeta^{T}$ is not the inverse of $\zeta$ (that is $\mu$), this is \emph{not} a diagonalization of $\alpha$. (As I erroneously claimed in Avi's office.) In particular, it does not imply that all matrices of the form $\alpha$ commute, so far as I know.
The lemma follows directly from the claim. On the one hand, if $f'$ is nonnegative, then $D$ is PSD, so we have, for any vector $v$,
\[ v^T \alpha v = v^T \zeta D \zeta^{T} v = u^T D u \geq 0 \ ,\]
where $u = \zeta^{T} v$.
On the other hand, if $f'$ is negative in some location, then clearly $D$ is not PSD -- we can take the vector $u$ to be any $e_i$ where $f(i) < 0$, and then we have $u$ such that $u^T D u < 0$.
Then, since $\zeta$ is invertible, we can find a $v$ such that $u = \zeta^T v$, and we have found a vector $v$ such that $v^T \alpha v < 0$.
Now, let's prove the claim, which is an application of M{\"o}bius inversion.
\begin{proof} [Proof of Claim]
Consider any entry of $\zeta D \zeta^{T}$, it is by definition
\[ \left(\zeta D \zeta^{T}\right)_{x,y} := \sum_{z \in P} \zeta_{x,z} \cdot D_{z,z} \cdot \zeta^{T}_{z, y} \]
\[ = \sum_{z \in P} f'(z) \cdot \zeta_{x,z} \cdot \zeta^{T}_{z, y} \]
\[ = \sum_{\begin{array}{c} z \in P \\ x \leq z \\ y \leq z \end{array}} f'(z) \]
Now we use the fact that $P$ is a lattice and not just a poset, so it has unique joins:
\[ = \sum_{x \vee y \leq z} f'(z) \ .\]
This value is clearly equal to $(\zeta f') (x \vee y)$, but since $f'$ is the M{\"o}bius inverse $\mu f$, by the principle of M{\"o}bius inversion this is just $f(x \vee y)$, or $\alpha_{x,y}$ as desired.
\end{proof}
\end{proof}
\end{document}