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

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

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