All entries for Wednesday 09 November 2011
November 09, 2011
Consider the definition of a graph – does this preclude the idea of a graph with 0 nodes? No, as both the set of vertices and the set of edges may be empty. This graph exists mostly to make you consider an extra case for every problem you do :)
How many automorphisms are there on the empty graph (how many isomorphisms from the empty graph to the empty graph)? This is equivalent to asking how many bijections there are from the empty set to itself. For a function to be well-defined, we only require that every element in the domain is mapped somewhere in the codomain – if the domain is the empty set, this condition is trivially true (if vacuous). It turns out the answer is one – the empty function.
I wondered about this a while in first year – how would you go about drawing a function if the first set in question was empty? – and I’m glad to see it’s actually something that’s been considered and given an answer.
Edit on 10/11 in reply to Nick:
Well, the definition of a matrix doesn’t preclude the existence of a 0×0 matrix, and I’d suppose that different matrices differ in at least one element, so I agree that that’s the only one.
The question on determinant is much more interesting due to how many different ways there are to approach it. Primarily, I want to check it doesn’t run opposite to my intuition in other areas.
Going back to the definition, we get that . would be the symmetric group on 0, having 0! = 1 elements (the empty function). So the determinant would be the sum of one number that was the product of no numbers. I’m of the opinion that the sum of no numbers is 1 (the multiplicative identity), so that would make the determinant one in this case.
Considered geometrically, the determinant represent area or volume in two or three dimensions. Extending backwards, we can get that the determinant of a 1×1 matrix acting on a line gives the length of the line under the transformation, and hence that a 0×0 matrix should act on a point. However, as the point is the entire space, this tells us nothing of what the determinant should be.
Considering that every matrix represents a linear transformation, and also that the empty function is bijective, we obtain that ( ) is nonsingular and hence the determinant isn’t 0, which is fine.
Going back to the definition I learnt in high school, where and determinants of matrices of dimension greater than two are defined using minors, cofactors and the above definition, let us try going backwards – can we see what the determinants of 1×1 and 0×0 matrices /should/ be based only on this? Expanding the 2×2 matrix above by the first row, we find that the determinant of (d) should be d and that the determinant of (c) should be c, which fits nicely with the actually definition in addition to the geometric one above. Expanding the 1×1 matrix by the first row, we require the determinant of any 0×0 matrix to be 1 (so that the determinant of the whole thing can be the sole entry), which also fits with our definition above.
But now the geometric line of thinking has lead me into vector spaces! To start, there is no vector space consisting of no vectors (fails presence of an identity). Consider the vector space consisting only of the zero vector. It is a vector space, but we cannot find a basis for it – the zero vector is not linearly independent. However, the vector space is at most of dimension 1 (it has one vector in it), but its basis of length one is linearly depedent, so removing the linearly dependent vectors, we obtain a basis of zero vectors. So this way (by a rather weak argument), the vector space consisting only of the zero vector has dimension zero, as we’d expect.