Aug 28, 2014
0 notes

Another random linear algebra problem, 2:

If \(X \hookrightarrow V\) as vector spaces, then denote by \(V^*\) \(\mathrm{Hom}_{\text{VectF}} (V,F)\) and by \(X^0\) the annihilator of the submodule \(X\) i.e. \(\{f \in V^* : X \hookrightarrow V = X \hookrightarrow \ker f \hookrightarrow V\}\).

Now, let \(T : V \to W\) a linear map between finite-dimensional vector spaces. Recall the transpose of \(T\) is the map \(T^t : W^* \to V^*\) by \(f \to f \circ T\). Show that

a) \(\mathrm{im}(T)^0 = \ker(T^t)\)

and

b) \(\dim \mathrm{im}(T) = \dim \mathrm{im}(T^t)\).

Proof of a). Let \(g \in W^*\) such that \(\mathrm{im}T \subseteq \ker g\). Since the category of \(\mathbf{R}\)-modules is abelian, and the assumption tells us precisely that the inclusion of \(\mathrm{im}T \hookrightarrow W\) factors through \(\ker g\), we write \(V \overset{g \circ T}{\to} R\) as

\[V \overset{\pi_T}{\to} \mathrm{im} T \hookrightarrow \ker g \hookrightarrow W \overset{g}{\to} \mathbf{R}\]

and since the right half of that chain of maps is zero, so is the entire chain of maps, i.e. \(\mathrm{im}(T)^0 \subseteq \ker(T^t)\).

Conversely, \(g \in \ker T^t \implies g \circ T = 0 \implies \mathrm{im} T \hookrightarrow W\) factors through \(\ker T\) by the universal property of kernels, and we are done.

b) Equivalently, we want \(\mathrm{im} T \simeq \mathrm{im} T^t\) as vector spaces. From the above it’ll suffice to show \((\mathrm{im} T)^* \simeq W^* / \mathrm{im} (T)^0\). Since we’re in finite dimension and vector spaces are free, this is equivalent to showing \(\mathrm{im} (T)^0 \simeq W^* / (\mathrm{im} T)^* \). Let \(\{x_1, \dots x_n\}\) be a basis of \(\mathrm{im} T\) in \(W\); extend it to a basis \(\{x_1, \dots x_n, w_1, \dots w_m\}\) of \(W\), and define the canonical map \(c:W \overset{\sim}{\to} W^*\) by \(b_i \mapsto \delta_i\) for each basis element \(b_i\).

Now, quotienting by subspaces corresponds precisely to making the basis of that subspace vanish. I claim \(\{w_1, \dots w_m\}\) is a basis for \(\mathrm{im}(T)^0\). Indeed, every functional in \(\mathrm{im}(T)^0\) has a representation \(\sum_{i \leq n + m} a_i \delta_i\) but by definition \(a_i\) is zero for every \(a_i\) corresponding to a \(c(x_i)\), which gives the isomorphism by identification. \(_\square\)

Aug 28, 2014
0 notes

Another random linear algebra problem:

Let \(V\) be a vector space over \(\mathbf{C}\) and let \(v_1, \dots v_n\) be eigenvectors of an operator \(T\) with distinct eigenvalues. Show that \(v_1, \dots v_n\) are linearly independent.

Clearly for any pair \((v_i,v_j) : i \neq j, v_i \not \in \mathrm{span}(v_j)\) since \(v_i = a v_j \implies \lambda_i v_i = a \lambda_j v_j \implies v_i = a \lambda_j / \lambda_i v_j\) but since the \(\lambda\)s are distinct, \(v_i \neq v_i\).

Now we make the following observation: if \(v_2, \dots v_m\) are linearly independent eigenvectors with distinct eigenvalues, then \(v_1\) another eigenvector with eigenvalue distinct from the others can’t lie in \(\mathrm{span}(v_2, \dots v_m)\), since

\[v_1 \in \mathrm{span}(v_2, \dots v_m) \implies v_1 = \sum_{2 \leq i \leq m} a_iv_i \implies Tv_i = \sum_{2 \leq i \leq m} a_i \lambda_i v_i \implies \sum_{2 \leq i \leq m} (a_i \lambda_i / \lambda_1 - a_i) v_i = 0 \implies\] (by independence of \(v_2, \dots v_m\)) \(\lambda_i / \lambda_1 = 1\) for each \(i\), a contradiction.

Then choose any pair of distinct eigenvectors \((v_i, v_j)\); the claim then follows by induction. \(_\square\)

Aug 28, 2014
22 notes
theapocalypticalgorithm:

lightprocesses:

Hyperbolic paraboloid

theapocalypticalgorithm:

lightprocesses:

Hyperbolic paraboloid

Aug 26, 2014
0 notes

One can

embed \(\mathcal{P}(X)\) (viewed as a poset category) contravariantly into \(\mathcal{P}(\mathrm{Hom}(X,X))\) by \(s \mapsto \{f : f(x) = x, \forall x \in s\}\); this is also a set-valuedpresheaf over \(X\) viewed as a topological space with the discrete topology.

Aug 26, 2014
1 note

For a friend:

We’ll show \(ab = \gcd(a,b) \cdot \mathrm{lcm}(a,b)\).

Let \(\rho(z)\) denote the set of distinct primes that divide \(z\). By the fundamental theorem of arithmetic every integer \(z\) admits a unique decomposition into prime factors, i.e. \(z = \prod_{p \in \rho(z)} p^{z_p}\).

One sees that

\[\mathrm{lcm}(a,b) = \prod_{p \in \rho(a) \cup \rho(b)} p^{\max(a_p,b_p)}\]

and that dually, \[\gcd(a,b) = \prod_{p \in \rho(a) \cap \rho(b)} p^{\min(a_p,b_p)}\]

and upon inspection, one easily sees that

\(\gcd(a,b) \cdot \mathrm{lcm}(a,b)\) divides \(ab\) and vice versa.

Aug 25, 2014
12 notes

alexyar:

shadowpeoplearejerks:

alexyar:

Need ideas for an expository talk in a nonspecialized graduate seminar.

Audience background: math grad students, most of them are numerical, math bio or analysis/PDEs. They might’ve heard the word “category”.

Time limit: 50 mins

Objective: talk about something cool for an hour

Real objective: expanding CV

Ricci flows? 

ugh, yeah, that’s something i need to learn anyway

on the other hand - ugh, geometry

presheafs and sheafs? they have a concise definition as a contravariant functor,

also you can make a bunch of toy models with finite sets because discrete topology

Aug 25, 2014
0 notes

Enumerating set-maps in Mathematica:

SetMaps[n_, m_] :=
Select[Subsets[SetProduct[Range[n], Range[m]]],
Length[#] == n && (Sort[First /@ #] == Range[n]) &]

Is there a faster way to do this (i.e. something besides applying an indicator function comprising some predicates to the power set of \(n \times m\)?)

edit: (where SetProduct[x_,y_]:=Tuples[{x,y}])
Aug 23, 2014
1 note

The Yoneda Lemma and Embedding

[Unearthing old blog posts; I can’t believe I spent a few days working out all the painful details of this proof last summer — J.]

…Now for the fun part. We’ll start with some definitions. Let \( \mathcal{C}\) be a locally small category, i.e. for all \( X,Y\) of \( \text{Ob}(\mathcal{C}), \text{Hom}(X,Y)\) is a member of \( \textbf{Set}.\) Let \( \mathcal{C}^{\land}\) denote the functor category from the dual of \( \mathcal{C}\) to \( \textbf{Set},\) so \( C^{\land} = \text{Fct}(\mathcal{C}^{op}, \textbf{Set}).\) Define \( h_\mathcal{C}\) to be the contravariant hom-functor, i.e. \( h_\mathcal{C} : \mathcal{C} \rightarrow \mathcal{C}^{\land}\) by \( X \mapsto \text{Hom}( - , X).\)

(The Yoneda Lemma) For \( X \in \text{Ob}(\mathcal{C})\) and \( A \in \text{Ob}(\mathcal{C}^\land),\) there is an isomorphism \( \text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X), A) \cong A(X).\)

Proof. To prove this, we’ll need to provide two morphisms, one in each direction and inverse to each other.

Construct a morphism \( \phi : \text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X), A) \rightarrow A(X)\) by the following chain of morphisms: \( \text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X), A) \rightarrow \text{Hom}_\mathbf{Set} ( \text{Hom}_{\mathcal{C}}(X,X), A(X)) \rightarrow A(X),\) where the image of a map \( f\) in \( \text{Hom}_\mathbf{Set} ( \text{Hom}_{\mathcal{C}}(X,X), A(X))\) under the final morphism is determined by the image of \( id_X\) under \( f.\)

Construct the morphism \( \psi\) in the opposite direction by associating with every element \( s \in A(X)\) a morphism between functors in \( \mathcal{C}^\land.\) Since a morphism between two functors (called natural transformations) is determined entirely by the evaluation of the functors at every object in \( \mathcal{C},\) we need only find for every \( s\) and every \( Y \in \text{Ob}(\mathcal{C})\) a map from \( \text{Hom}_\mathcal{C} (Y,X) \rightarrow A(Y),\) which is given by the following chain of morphisms: \( \text{Hom}_\mathcal{C} (Y,X) \rightarrow \text{Hom}_\textbf{Set} (A(X), A(Y)) \rightarrow A(Y)\) where the final map is determined, similar to the above, by the image of \( s \in A(X).\)

We verify that \( \phi\) and \( \psi\) are inverse to each other, i.e. \( \phi \circ \psi = id_{A(X)}\) and \( \psi \circ \phi = id_{Hom_{\mathcal{C}^\land}(h_\mathcal{C}(X),A)}.\) Since we’re working with stuff in \( \textbf{Set},\) it’s enough to look at elements. Let \( s \in A(X).\) Now, \( \psi (s)\) is a morphism (natural transformation) between functors, and the first map from the chain of morphisms (call it \( a\)) from which we built \( \phi,\) namely \( \text{Hom}_{\mathcal{C}^\land} (h_{\mathcal{C}}(X),A) \overset{a}{\longrightarrow} \text{Hom}_\textbf{Set}(\text{Hom}_{\mathcal{C}}(X,X), A(X)),\) evaluates that functor at \( X \in \mathcal{C},\) and the final map takes a map from that hom-set to wherever \( id_X\) is taken. So, let \( f_X\) be that map, i.e. \( a (\psi (s)) = f_X \in \text{Hom}_\textbf{Set} (\text{Hom}_\mathcal{C} (X,X), A(X)).\) Then we have

\( (\phi \circ \psi) (s) = a( \psi(s)) (id_X) = f_X (id_X).\) But \( f_X\) is precisely the chain of morphisms \( \text{Hom}_\mathcal{C}(X,X) \rightarrow \text{Hom}_{\textbf{Set}}(A(X),A(X) \rightarrow A(X)\) (since \( a\) evaluates the functor at the object \( X\)) where the last map is associated to the image of \( s \in A(X).\) So what happens when you feed \( id_X\) into this chain of maps? \( id_X\) is lifted to \( id_{A(X)}\) (since \( A\) is in the functor category); the final map in the chain takes everything to whatever \( s\) is mapped to, which is \( id_{A(X)} (s) = s,\) so we have that \( \phi \circ \psi (s) = id_{A(X)} (s),\) for all \( x.\)

For the other direction, let \( Y \in \mathcal{C}\) and \( \sigma \in \text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X),A).\) We want to show that \( \psi \circ \phi = id_{Hom_{\mathcal{C}^\land} (h_\mathcal{C}(X),A)}.\) Since \( \sigma\) is a morphism between (contravariant) functors, i.e. a natural transformation, it’s really just a collection of morphisms \( \sigma_Y\), one for each object \( Y \in \text{Ob}(C),\) such that, for any morphism and any \( N,M \in \text{Ob}(\mathcal{C}),\) we have that \( g \in \text{Hom}(M,N)\) the following equation holds (there’s an associated commutative diagram that I can’t figure out how to implement in Wordpress’ TeX extension): \( A(g) \circ \sigma_M = \sigma_N \circ h_\mathcal{C}(X) (g).\)

Now, since any natural transformation \( \sigma\) is determined by its \( \text{Ob}(C)\)-indexed collection of morphisms \( \{ \sigma_Y \},\) then \( \psi \circ \phi = id_{\text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X),A)}\) if and only if for each \( Y \in \text{Ob}(C), (\psi \circ \phi (\sigma))_Y = \sigma_Y.\) (Recall that our constructed morphism \( \psi\) constructs such a \( Y \in \text{Ob}(C)\)-indexed collection of morphisms for each element of \( A(X).\)) Again, since we’re working in hom-sets, it’s sufficient to look at elements of our sets; in this case, they’re maps in \( \text{Hom}_\mathcal{C}(Y,X).\) Let \( g\) be such a map. Then, observing that the first morphism of the chain from which we constructed \( \phi\) takes \( \sigma\) to the morphism \( \sigma_X,\) and the next morphism simply evaluates \( \sigma_X \) at \( id_X,\) i.e. \( \phi (\sigma) = \sigma_X (id_X),\) we now have that

\( \psi \circ \phi (\sigma) = A(g) (\sigma_X (id_X))\) (Since, similarly to the preceding observation, the first map in the chain of morphisms from which we constructed \( \psi\) merely takes morphisms to their image in \( \textbf{Set}\) under the contravariant functor \( A,\) and the next morphism evaluates that image at \( \psi\)’s original argument.) Well, hmm. This certainly looks like the definition of a natural transformation between contravariant functors, doesn’t it? We then have

\( A(g) (\sigma_X (id_X)) = A(g) \circ \sigma_X (id_X) =\) (by the definition of a natural transformation) \( (\sigma_Y \circ h_\mathcal{C}(X)(g)) (id_X).\) Recall that \( h_\mathcal{C}\) is the contravariant hom-functor that fixes an \( X \in \text{Ob}(\mathcal{C})\) in its second argument, i.e. for all morphisms \( f \in \text{Hom}_\mathcal{C}(N,M), h_\mathcal{C}(X) (f) : \text{Hom}(M,X) \rightarrow \text{Hom}(N,X)\) by \( g \mapsto g \circ f\) for every \( g \in \text{Hom}(N,M).\) We then have

\( \psi \circ \phi (\sigma) = A(g) (\sigma_X (id_X)) = (\sigma_Y) \circ h_\mathcal{C}(X)(g)) (id_X) = \sigma_Y \circ (id_X \circ g) = \sigma_Y \circ g,\) for every \( g \in \text{Hom}(Y,X).\)

Then \( \phi \circ \psi = id_{A(X)}\) and \( \psi \circ \phi = id_{Hom_{\mathcal{C}^\land}(h_\mathcal{C}(X),A)},\) so we have our isomorphism, as desired. \( \square\)

Now, we can establish the Yoneda embedding.

(The Yoneda embedding) The functor \( h_\mathcal{C}\) is fully faithful; we call it the Yoneda embedding. In particular, we can fully embed a locally small category \( \mathcal{C}\) inside its associated category \( \mathcal{C}^\land\) of contravariant set-valued functors, i.e. \( \mathcal{C}\) is a full subcategory of \( \mathcal{C}^\land.\)

Proof. For \( X,Y \in \text{Ob}(\mathcal{C}),\) we have \( \text{Hom}_{\mathcal{C}^\land}(h_\mathcal{C}(X), h_\mathcal{C}(Y)) \cong h_\mathcal{C}(Y)(X) = \text{Hom}_\mathcal{C} (X,Y).\) \( \square\)

Generalizing Cayley’s Theorem

(Generalizing Cayley’s Theorem) Let \( G\) be a group. Construct a (very) small category \( \mathcal{G}\) with one object, say \( A,\) and let the elements of \( G\) become \( \text{Hom}_\mathcal{G} (A,A).\) Due to the existence of inverses, everything in \( \text{Hom}_\mathcal{G}(A,A)\) is an isomorphism (in the category-theoretical sense.) [I’d like to note here that we don’t really care about what \( A\) is or what its elements are, or if \( A\) is even a set. To construct a category, we only need objects and morphisms. Pretty neat, right?] We call a category \( \mathcal{G}\) constructed in such a way a groupoid, for obvious reasons. An important property is that \( \mathcal{G}\) is self-dual: \( \mathcal{G} = \mathcal{G}^{op}.\) Now, we can apply Yoneda in two ways. Every morphism \( f \in G = \text{Hom}_\mathcal{G}(A,A)\) gets sent to a unique natural transformation \( f*\) from \( h_\mathcal{G}(A)\) to itself; since \( \mathcal{G}\) only has one object, for each \( f\) there’s a unique set-isomorphism \( f*_A\) associated with \( A\) that satisfies \( f*_A \circ h_\mathcal{G} (g) = h_\mathcal{G} (g) \circ f*_A\) for each \( g \in G.\) Fix \( f = id_G.\) Since functors preserve isomorphisms identity and composition of morphisms, it becomes an easy verification to check that every element of \( G = \text{Hom}_\mathcal{G}(A,A)\) is mapped to a set-isomorphism (an automorphism, cough, cough, permutation) from \( h_\mathcal{G}(A)(A) = \text{Hom}_\mathcal{G}(A,A)\) to itself, and that this inherits \( G’s\) group structure.

Alternately, we can apply the Yoneda lemma directly: let’s also use the first half of the isomorphism \( \phi\) from above. We then have have

\( \text{Hom}_\mathcal{G} (A,A) \cong \text{Hom}_{\mathcal{G}^\land}(h_\mathcal{G}(A), h_\mathcal{G}(A)) \rightarrow \text{Hom}_\textbf{Set} (\text{Hom}_\mathcal{G}(A,A), \text{Hom}_\mathcal{G}(A,A)).\)

where the final map must be an injection because \( \phi\) was an isomorphism in the category \( \textbf{Set}\), hence bijective, hence injective. Well, what does this tell us? We’ve managed to embed \( G\) into the set of all maps from the underlying set of \( G\) to itself. Clearly that set contains the symmetric group \( S_{|G|}\) of all isomorphisms from the underlying set of \( G\) to itself, and since functors preserve isomorphisms everything from \( \text{Hom}_\mathcal{G}(A,A)\) maps to an isomorphism, so we’ve embedded \( G\) into \( S_{|G|},\) as desired. \( \square\)

Aug 23, 2014
0 notes
The identity group element corresponds to the identity permutation. All other group elements correspond to a permutation that does not leave any element unchanged. Since this also applies for powers of a group element, lower than the order of that element, each element corresponds to a permutation which consists of cycles which are of the same length: this length is the order of that element.
Wikipedia, Remarks on the regular group presentation \(G \hookrightarrow \mathrm{Sym}(|G|)\).
Aug 23, 2014
0 notes

A brief linguistic note:

A subcategory is full if its hom-objects are isomorphic to their ambient hom-objects.

A functor is full if its induced map between hom-objects is epic.

The stipulation that a functor preserves identity maps can be dropped (and recovered) if the functor is full (by the uniqueness of identity, since \(\mathrm{id}_A = \mathrm{id}_A \mathrm{id}_A’ = \mathrm{id}_A’\)).

(In particular, \(\mathcal{F}(\mathrm{id}_A)\) acts like an identity inside the image of \(\mathrm{Hom}(A,A)\) under \(\mathcal{F}\), so once you have fullness you get \(\mathcal{F}(\mathrm{id}_A) = \mathrm{id}_{\mathcal{F}(A)}\).

Navigate
« To the past Page 1 of 35
About
Repository for math-related links, anecdotes, code, and random thoughts. Subscribe via RSS.