A problem
Let A and B be connected subsets of [0,1]2 where π(A) = [0,1] = π(B) where π is the projection map π(x,y) = x. We construct a new set C out of A and B as follows.
Let C = {(x,y,z) | (x,y) ∈ A and (x,z) ∈ B}.
Is C connected always? If not then are there counterexamples?
Read below to see an answer.
Read more…
matrix commutators
We know that set of commutators of matrices is exactly the space of matrices of trace zero and has dimension
. I discuss an interesting question related to this which was brought to my notice by Anamika:
Given a matrix of trace zero can we construct two matrices
and
of determinant
, such that
. Here is a proposed way of finding matrices
and
such that
.
It turns out that this problem has a variety of applications and it goes by the name Sylvester equation (after fixing one matrix say A). For example, it is used in Computer Vision to estimate the pose(position, orientation ) of an object based on a series of images. See video here
We first try a simple case: Suppose is matrix with non-zero entries only in the diagonal and at locations
for
(like in the Jordan Normal form) with
or
. We want to find a matrix
such that
where
is a
matrix with trace zero. We equate the
entries on both sides to get,
expanding we get
Now if denotes the operator that flattens the rectangular(column-wise) matrix to a column vector then we need to solve the system.
where,
We can solve the system provided
has maximum rank. We can reconstruct
from
but this does not ensure that the matrix
is of determinant
. We can ensure that
has determinant
by addition of a suitable scalar times identity matrix ( which must also be a solution trivially)
Wikipedia mentions that there is a better way to represent this matrix using tensor product ( also called Kronecker product of matrices http://en.wikipedia.org/wiki/Kronecker_product):
where is the
identity matrix.
0.1. Related results
On a related note, here is another question. Can you produce matrices and
such that the commutator
is the sum of two other
commutators
and
? . Using the methods above we can find
and
indirectly, but is there a simple representation of
and
in terms of
? I do not know. However here are some insights:
Suppose denotes the matrix with
only at the position
, (
), in the matrix and the rest filled by zeros. We use the fact that the set of
matrices which are commutators is a linear space with basis:
and
I will leave this to the diligent reader to see why this is true. This says that any commutator
is a linear combination of these basis vectors. Armed with this result we can break the original problem down to the following two problems:
- Given matrices
matrices
with commutator
, the commutator
(
) and a scalar
, find
and
such that
.
- Similarly given a scalar
, and matrices
, for each
, find matrices
such that
I could not give a simple representation of in terms of
. For for some special cases, it seems possible. Suppose you know that for the index
,
is the only column of
containing non-zero entries. Now choose constants
,
, such that
.
We next note the identity , for
and
, using which we can write:
where denotes the entry at the location
in the matrix
. Now let
. Next using the fact that
is
, we have
and
, so the above expression for
can be rewritten as:
or,
where . Now if
, then
Thus,
Here are other examples: For ,
,
,
Also, for the case where and
, we have:
Three non-idiotic guesses
Three problems to ponder for the next 100 years:
- First one may seem contrived but thinking about this would hightlight some major properties of primes. So here it is : The number 82 is the largest positive number that cannot be written as sum of two square free numbers each having odd number of prime factors.
Motivation for this guess comes from the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 + moebius(n-i) )/4 );
return sum;
The graph which shows the number of ways of writing a number as a sum of two such square free numbers, reveals a trend:it increasingly stays away from zero. In fact after taking off from 82, where it is zero, it never seems to drop down.Note that we can always write a number as a sum of two square free numbers. The numbers of ways of writing them is:
. Have to warn you that I have not seen an actual proof but I have seen it mentioned here:
A098235 - The second one is in the same spirit as the previous one. Any even number > 10 can be written as the sum of two square free numbers with one having odd number of prime factors and the other having even number of prime factors.
Motivation for this guess comes from the the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 – moebius(n-i) )/4 + ( 1 – moebius(i))*( 1 + moebius(n-i) )/4);
return sum;
As with the previous conjecture the graph which shows the number of ways of writing a number as sum of such square free numbers. has only a few hiccups taking off, and at n=10 it achieves escape velocity. I should also mention here that any even number according to Chen Jigrun can be written as the sum of prime and semi-prime(product of two primes) or a sum of two primes. So when diluted, this result that says if Goldbach conjecture were false, we atleast know that every even positive number can be written as sum of two square free positive numbers one with odd number of prime factors( infact 1) and the other with even number of factors ( in fact 2). - Treat the following with caution please. If
denotes the Euler totient function, then the following number is always greater than 2n.
.
Proving this will prove the Goldbach conjecture. This is because, it is only when both i and 2n-i are prime that:is 1. There are better ways to reformulate the Golbach conjecture. One other way is the following:
Given an even number $2n$, there exists a numbersuch that
A bound for matrix norm
We wish to better the bounds for the norm of a matrix with scalar entries when it defines a linear map with from
to
, that is the series ,
is convergent for each and
. The standard bounds for matrix norm given in the text for
, are
and
, for
spaces. We give yet another bound using the power mean inequality:
Consider positive weights ,
which have total mass
, then for nonnegative real numbers
,
and for all
one has
2. Bound for matrix norm
Consider,
where for some fixed and
,
.
Now we use power mean inequality with { and }
,
{ and }
. So,
Now if we take,
Then we have . So we have infinite number of bounds for the norm as we vary
among positive reals (of course, not all values of
might be useful )
Example : Consider the matrix
For this matrix and
is also infinity, however
is finite with
. This is because
and
. Thus
.
You can further see that is a better bound than
always, since if we take
and
, we have
where we have used the fact that .
Presentations and cardinality
Have a look at the presentation of a group defined by the generators , and the presentation below.
and relations:
Proposition 1 (Higman) Let
be the group defined by the four generators
and the four relations in 0. Then
- Each subgroup of finite index in
is equal to
![]()
is infinite.
Proof: We first prove a). Every subgroup of finite index in
contains a normal subgroup of finite index ( the kernel of the action of the group
on the cosets of
which is the intersection of the conjugates of
; the action induces a homomorphism of
into a finite sysmmetric group, so the index of the kernel in
must be finite as well). It therefore suffices to prove that
does not have any finite non-trivial quotient. Now suppose
is such a quotient and let
be the order of
in
. Note that not all
can be
since we had assumed that
is non-trivial. Now let
be the smallest prime divisor of any of the
, and suppose without loss of generality that
divides
. The fact that
and so and thus also
. This implies that
. On the other hand, we have
. Let the order of
in in
be
. Clearly
. Thus
. If
is a prime factor of
we then have
and
, which contradicts the minimal character of
, hence a). Proof of b). Let
and let be the sub-groups generated by
resp. in
. The groups
are each isomorphic to
and
. Similarly one can define the group
(
) with subgroups
and
(resp.
and
).
The key idea now is to recognize that the presentation gives us a recipe for forming the amalgam:
The result now follows by the fact that the free product which is also a subgroup of
is infinite.
For proving that the group whose presentation is given by 0 collapses, the methods employed are more elementary:
has three generators
and defining relations 0 We must then have from the first relation:
Raising both sides of the first relation to the -th power, we have
and therefore,
and similarly also from the second and third relations we have,
Conjugating the third relation by , the left-hand side becomes
While the right hand side becomes
So we have,
or
Multiplying (3) by gives
and
But by raising the first relation to the power 3 we have
Thus
Similary, we also have
. Finally, conjugating the first relation with we must have on the left hand side
while on the right hand side we get,
Thus . Again, from the first relation this implies
or
. Then from the third relation we must also have
or
and so also
or
. The group formed by these generators hence collapses.
Embedding a torsion-free group in a infinite simple group
Using the HNN theorem we have an easy corollary.
Corollary 1 Every group can be embedded in a group
enjoying the following properties.
- All elements of
of the same order are conjugate.
- Furthermore, if
is denumerable (or torsion-free) we can choose
to be denumerable( or torsion-free)
Proof: For a change, Serre was kinder with me in this proof. So lot of the content here are his words. If have the same order there exists an injective map from
to
which sends the generator
to
. The HNN theorem gives us a group
in which both
and
are conjugate. Repeating this operation for every such pair of
which have same order in
, we construct, bigger and bigger groups, whose direct limit (their union) is a group
containing
, in which every pair of elements with same order in
(identified with theire images in
) are conjugate. Now we repeat this procedure on
to get a bigger group
where every pair of elements of
( identified with their images in
) which are of the same order are conjugate to each other. After
such steps we get a group we denote by
in which every of elements of
of the same order are conjugate. Passing to the direct limit (union) we claim that the direct limit
in which every pair of elements which are of the same order are conjugate. For if,
which are of same order then
for some
, so
must be conjugate to each other in
by construction. So the group
answers the question.
Why is torsion-free (denumerable) if
is torsion free (denumerable)? This is because HNN extensions may be chosen to be torsion-free (denumerable) if the group whose extension is being taken is torsion-free ( denumerable). Also, direct limits of an increasing sequence of groups is also torsion free( or denumerable) if the groups are so. In particular if
is torsion-free, every pair of elements must be conjugate to each other. This means if
is any normal subgroup of
and
then as every element conjugate of
must be in
, and the set of conjugates of each
is the entire group
,
. So
is simple if it does not reduce to
. Cute!
HNN Extensions
I have been studying amalgams from the book Trees ( vying for time with five other courses) with little progress. Serre, the author of this book, is absolutely merciless on the reader, leaving out all details that a stout hearted reader, who is motivated enough can fill in( maybe a background in decrypting ciphers will help). The answers are there in book, but hidden behind some carefully crafted words, and God knows ploughing through this thick crust of words is not easy. But after about fifteen to sixteen readings(read boxing rounds) of the proof, matters usually settle down without anyone being mortally wounded with the dawning of the realization that I understand the proof well-enough to write it myself.
I will try to fill in the details in this post and few others. I will start with a construction I particularly liked (it is a twelve line proof in Trees). This proof is one that elaborates on the proof given in Trees(the mistakes, are well, most likely to be mine).
Proposition 1 (G. Higman, B.H Neumann, H. Neumann) Let
be a subgroup of a group
and
an injective homomorphism. Then there is a group
containing
and an element
of
such athat
for all
. Furthermore, if
is denumerable( or finitely generated, or torsion free) we can choose
to be a group with the same property.
Proof: For each , we put
and
. By amalgamating
with the injective homomorphisms:
and
( id is is the identity map), we construct the group
:
Let for
, be the homomorphisms obtained by the amalgamation. Recall that in constructing amalgams we take the quotient of a free group formed of the disjoint union of these sets, so
for
are different subgroups of
. Let
be the canonical isomorphism:
. These maps induce the maps
for
. The homomorphisms
are also compatible with maps
and
because
By the universal property of amalgams, we have a induced map that makes the diagram below commutative:

A similar argument shows that the inverse maps
induce the map . Now as
. We show that we also have
. This will show that
is an automorphism between
and
. To see this note that the maps
so for all , we have
Thus the homomorphisms are each compatible with the maps
and
from each
. So, these maps must induce a unique homomorphism
from
to
such that
. Both the identity map also
are homormophisms from
to
which satisy the above conditions, by uniquenesss of the induced isomorphism (universal property of the amalgam), we must have that
. By a similar reasoning using
, we must also have
. Thus
is indeed an automorphism.
Further by commutativity of the diagram we must have in particular that
. Thus, if we identify groups
with
,
with
and
with its images in
, the map
is just an extension of the map
.
The construction of group is now fairly easy. If is the infinite cyclic group generated by
, we form the semi-direct product
, with
acting on
via
by conjugation as follows
Clearly when we restrict this action to we have for any
:
The pair then has the desired property.
Moreover if is denumerarble, then
is also denumerable being the quotient of the disjoint union of denumerable groups. Next as
has the same cardinality as
,
must also be denumerable. If
is without torsion, we would like to show that
is also without torsion. For this, we first prove by induction that for all
the group
is without torsion. This is clear for as from the structure theorem, the only elements of finite order in the amalgam
, are those that are conjugate to either
or
, both of which are without torsion. Now assume the that this is true for all natural numbers less than
. Then for
, use associativity of amalgams( proved in previous post) to write
Notice that is without torsion as
(by induction hypothesis) and
also is without torsion. Also as
and
are without torsion so is
is also without torsion. Thus for all
,
is without torsion. Now by passing to the direct limit of the groups
, we see that the direct limit
(being the union:
) is also without torsion. Moreover, the infinite cyclic group
is also without torsion and so the semidirect product
as its elements are of the form
where
and
. If
, for any
we have
and if
, then for any
,
for some
.
Finally we show that if is finitely generated, so is
(in a later post)
associativity of amalgams or why universal properties can be powerful
Amalgams of groups are examples of what are known as colimits in category theory(aka abstract non-sense). With abstract non-sense, you can turn a blind-eye to the structure of the groups and concentrate wholly on its social behavior, determined by its universal property. There is nothing deep about proving results using universal properties of groups, as we are using the most obvious properties of groups when interacting with other groups. But these can be super-powerful when it comes to proving stuff which would otherwise be non-trivial ( for example when you are only looking at the structure of these groups).
Recall that the product of groups where
, amalgamated with groups
using injective homomorphisms
and
for
is the group
along with homomorphisms
that are compatible with
and
. This means that
for all
. Further,
has the universal property that if
is any group with homomorphisms
which are compatible with the maps
for each
, we have a unique homomorphism
such that:
The group is usually denoted by
. To illustrate the power of this definition, lets us prove the following assertion about associativity of amalgams.
Note that the amalgam is exactly the group that makes the following diagram commute and

whats more important: it is best candidate for making the diagram commute in the sense that, if is any other group replacing
that also makes the above diagram commute then there is a unique homomorphism from
to
. Such a
is hence unique upto a unique isomorphism. To prove the above equality we try to show that LHS also has the universal property of the amalgam RHS and hence there must be a unique isomorphism between the two. Consider the diagram below:
With the amalgam we have homomorphisms
and
and the with amalgam
we have homomorphisms
.
Now if is any group with maps
for
, that are compatible with
, then we need to show that
factors via a unique homomorphism
.
.
The map and
are compatible with
and
so by universal property of the amalgam
we have a unique morphism
such that
. Now since
are compatible with
and
, the map
can be further factored using the universal property of the amalgam
by the unique homomorphism
. This shows the associativity of amalgamation.
Note 1: When amalgams were first introduced, before category theory came into being, (see for example pre-ww-2 era papers by B.H Neumann on free groups with amalgamation et. al), they were treated as generalized versions of free products of groups with complicated inner structures. They never made use of these elegant universal properties and proving such things as associativity, can get really messy.
Updated:Fixed typo
cheat sheet for continuity.
You are interested in establishing the continuity of a linear map where
and
are normed spaces. You would like to know some sufficient conditions for proving continuity. The thought about browsing your old fat text book makes you cringe and would like a quicker way (like what a Schaum series textbook would offer). Heres a list
- Continuity at zero.
- Existence of a positive
such that
.
- Did you know that if
and
are Banach, thanks to the venerable Closed Graph Theorem, it is sufficient to check that
is closed for proving its continuity.
- Is the range space your linear map finite dimensional?. In this case it is enough to check that the null space of your linear map is closed.
- Is your map a projection map? If yes, then it is enough to check that range space and zero space of your linear map are closed.
Btw Iam a fan of the Schaum series books. They explain the basics in as little notation as possible and with little to and fro references.Even Gian Carlo Rota sings paens about them(well, he likes atleast one book). Come join the league of fans, don’t be snooty…
which random variables have uniform distribution
Sometime back I was asked this question by our professor teaching us probability : How do we characterize random variables which have uniform distribution?. I revisited my old measure notes to give a partial answer to this question:
Let be a random variable defined on the probability space
with Lebesgue measure. Suppose further that
is the union of disjoint intervals
where in each interval
we have either
or
a.e. Then, a necessary condition for
to have the uniform distribution is the following. For each
we have
a.e ().
Proof: Let , then if
is the probability measure (lebesgue measure) on
. Let
be the intnervals where
a.e or
. Then,
where the last equality holds by m.c.t ( denotes the indicator function). Let
for
then note that the restriction of
to
( which we denote by
) is 1-1, so
makes sense and its derivative exists so by change of variables we may write,
So,
But the density function of is
as
is given to have the uniform distribution, the integrand on the right must be
a.e. Thus, for almost all
,
Here is a simple example: Consider the random variable as shown in the diagram which has uniform distribution. Notice that for each
in the range of
, that is not in 0 or 1, the sum of the inverse of slopes at each point where
assumes the value
is
.
|

