For reasons which the margin of this page is too small to hold, I have been reading parts of a recent paper by O. Selim


*On submeasures on Boolean algebras*, arXiv [1212.6822v3](http://arxiv.org/abs/1212.6822v3)


and in Section 7 the following technical lemma is given (Lemma 7.5 in the paper)


**Lemma (paraphrased)** Let $S$ be the set of *non-empty* subsets of some fixed finite set $F$, and consider the matrix $A:S\times S\to {\mathbb Q}$ where
$$ A\_{I,J} = 1 \hbox{ if $I\cap J\neq \emptyset$, and }
 A\_{I,J} = 0 \hbox{ if $I\cap J = \emptyset$.} $$
Then $A$ is invertible.


Selim gives a proof by induction that the columns of $A$ are linearly independent, but he says "we could not find a particularly enlightening proof". So my question is this: do we have a more conceptual argument to show this (real, symmetric) matrix is invertible?




---


[**EDIT/UPDATE 2012-03-07:** this was poorly phrased on my part; I was hoping to find some explanation that involved the lattice or group stucture on $\{0,1\}$, and which took advantage of the very particular structure of this matrix, although I am grateful for all answers received so far. In some sense I wanted to know: *"what is the pattern?"* or *"what is the underlying algebraic mechanism?"* -- the matrix is defined in terms of some incidence or order structure, so does that give some way to interpret invertibility of this matrix as part of a more general result? (I do not mean a result like "a matrix with non-zero determinant is invertible".)


Benjamin Steinberg's answer comes closest, at present, to what I was hoping for, but Benjamin Young's answer is also very suggestive and helpful.


I suspect this will be routine for several MO regulars, but hope it is not too elementary or "too localized".




---


**[older comments/thoughts, left here for context]**


My vague thoughts are that one could view $A$ as the corner of a square matrix indicated by the power set of $F$, and then perhaps do some kind of Fourier transform on the group $\{0,1\}^{|F|}$. Or perhaps there is some kind of Möbius inversion at work here?


While I'm here, a question on terminology: the matrix $A$ is of course the adjacency matrix of a certain graph whose vertex set is $S$. Does this graph have an established name?



Invertibility of a certain matrix indexed by the Hamming cube
The argument of Kim and Roush looks as follows after translating out the semigroup theory (and is essentially using a Mobius inversion idea).


Let $T\colon \mathbb Z^S\to \mathbb Z^S$ be the group homomorphism corresponding to left multiplication by $A$. We show that in appropriate bases for the domain and codomain the matrix of $T$ is triangular with 1s on the diagonal and hence $A$ is invertible over $\mathbb Z$. Let $e\_X$ be the unit vector corresponding to a non-empty subset $X$ of $F$. Put $e\_{\emptyset}=0$ for convenience. Let $b\_X=e\_F-e\_{X^c}$ where $X^c$ is the complement of $X$. Notice that $b\_F=e\_F$ and hence the $b\_X$ form a basis for $\mathbb Z^S$. 


Now one computes $$Ab\_X=A(e\_F-e\_{X^c})=\sum\_{Y\subseteq X} e\_Y.$$ If we use the $b\_X$ with $X\in S$ as a basis for the domain of $T$, the $e\_X$ with $X\in S$ as a basis for the codomain and total order $S$ by a topological sorting of $\subseteq$ then the matrix for $T$ with respect to these bases is triangular with 1s on the diagonal. Thus $A$ is invertible over $\mathbb Z$.


