Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that X and Y are finite sets and that f : X → Y is an arbitrary map. Let PB denote the pullback of f with itself (in the category of sets) as displayed by the commutative diagram

PB → X
↓      ↓
X   → Y

Terence Tao observes in one the comments on his weblog that the product of |PB| and |Y| is always greater than or equal to |X|2. (This is an application of the Cauchy-Schwarz inequality.) This fact may be rephrased as follows: If we ignore in the above diagram all arrows and replace the sets by their cardinalities we obtain a 2x2 matrix with a non-negative determinant.

The question is whether this is a general phenomenon. Suppose that n is a positive integer and that X1, X2, ... ,Xn are finite sets; furthermore we are given maps f1 : X1 → X2, f2 : X2 → X3, ... , fn-1 : Xn-1 → Xn. We construct a pullback diagram of size nxn. The diagram for n=4 is shown below.

PB → PB → PB → X1
↓       ↓       ↓     ↓
PB → PB → PB → X2
↓       ↓       ↓     ↓
PB → PB → PB → X3
↓       ↓       ↓     ↓
X1 →  X2 →  X3 → X4

Here, the maps between the Xi in the last row and column are the corresponding fi and the PBs denote the induced pullbacks. (Of course, although they are denoted by the same symbol, different PBs are different objects.) The PBs can be constructed recursively. First, take the pullback of X3 → X4 ← X3; it comes with maps X3 ← PB → X3. Having constructed this, take the pullback of X2 → X3 ← PB and so forth.

Ignore all arrows and replace sets by their cardinalities. Is the determinant of the resulting nxn matrix always non-negative?

share|improve this question
    
I can't help but feel like you should be using the Gessel-Viennot lemma. –  Qiaochu Yuan Oct 22 '09 at 14:04
    
Interesting approach. By the way, I can prove that it is true for n=3, but this was already some effort. I hope one can read the diagram. –  Philipp Lampe Oct 22 '09 at 14:52
add comment

1 Answer

up vote 10 down vote accepted

Write Xn = {x1, ..., xk}. For each 1 ≤ i ≤ k let wi be the vector whose jth component is the cardinality of the inverse image of xj in Xi. Then your matrix is the sum w1w1T + ... + wkwkT, a sum of positive semidefinite matrices, so it is positive semidefinite and in particular has nonnegative determininant.

share|improve this answer
    
Great. What a simple argument. –  Philipp Lampe Oct 22 '09 at 17:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.