The older I get, I realised that I am getting more capable to care less of what people think of me, except from those I care about. It is becoming easier for me to disregard ignorant or harsh comments from people outside that circle. This sounds like a good change, but I was not entirely happy with the journey. It took me a while to realise that my definition of ‘care less’ was wrong.
I was a sensitive guy. My reliance towards my feeling was strong, despite my academic background which is heavily dependent on logic and rigour, to which I am still quite baffled. I took pride in my ability to empathise with a great number of people, which I didn’t find common amongst my circle of friends. It made me feel good about myself: this ability was one of the reasons I felt unique and I strived to be empathetic every single time. However, it wasn’t all sunshine and rainbows. Sometimes I ended up getting used by my friends, although I would like to think it was unintentional, to solve their problems. In the case where I genuinely wanted to help solve theirs, it would frustrate me when I couldn’t do anything about it.
I am slowly directing myself towards the other direction, to which I have a mixed-up feeling. On one hand, I feel more at peace with myself. I can focus more to my own problems instead of spending more time and energy solving others’. I am also becoming more appreciative towards the power of listening: to simply be there for someone and listen. On the other hand, there is always this constant uneasiness that I have become more aloof, that I have deviated from whom I aspired to be. This is the reason why I wasn’t happy with the change. Something is not quite right but I had no idea what caused it.
My initial guess was that I am disappointed a lot of times by people. Every time it happens, I couldn’t help but blame myself from having an expectation in the first place. It is quite a dilemma for me: not expecting at all is utterly impossible, but expecting something would most likely end up with me getting hurt. My most natural response was to be less empathetic towards people. I shielded myself from any future unnecessary disappointment by being less caring. If I will end up being disappointed anyway, why bother putting an effort to care for someone in the first place? For the first time in my life, I no longer aspired to be an empathetic person.
Obviously there is something wrong with that train of thought. The fact that I know it’s wrong but I couldn’t exactly pinpoint where the problem is frustrates me. It took me a while to arrive at this conclusion: I have been victimising myself while in fact it is my motivation that is corrupt. I feel I deserve to be treated the same way I have given my love and demonstrated my affection towards someone. I ask them to return the favour. I am not as selfless as I thought and it saddens me. Something that I have always thought as unique turns out to be crooked.
It is the subtlety of my corrupt motivation that I figured worth sharing. When you do good to others, it might be totally possible to subconsciously expect something good be done to you in return. I am of the opinion that no matter how hard we try not to do it, we are not going to be truly free from it. We’re humans after all. I am now just trying not to motivate myself to be selfless. The selfish nature of ours will always be existent. All we can do is to minimise its occurrences.
Ideally, caring less of what people think of you should be driven by the awareness that we cannot and must not please all people. We can still be empathetic and having the aforementioned awareness at the same time. Compassion should be always on the table for as long as we live. We don’t have to be aloof to care less.
To value the importance of being empathetic towards people, I was put in a situation where I gave it up, until I realised that it does matter. Life is funny that way.
Sometime ago, in my research, I came across a matrix map I am interested at. It is a generalisation of the complex map
defined on a complex projective plane .
Let be a field. Given a skew-symmetric matrix , i.e. , one can define the Cayley transform of , denoted by , as
for all such that is invertible.
If we were somewhat more restrictive in our assumption about , which in this case is to consider an ordered field, then is always invertible for all skew-symmetric matrix . To see this, suppose it is not, then there exists a non-zero such that , i.e. . However,
which implies . Since we are working in an ordered field, this forces , a contradiction.
It can be shown that is an orthogonal matrix, i.e. where is the identity matrix of the same size. It’s not hard to see this by direct computation:
In the proof above, we used the fact that commutes with . Moreover, because
Proposition. The map is an involution, i.e.
Example. If , then
for some satisfying . If , then
for all such that .
In Lie group and Lie algebra notation,
where is the Lie algebra of skew-symmetric matrices equipped with the usual Lie bracket, the Lie group of orthogonal matrices, and a subgroup of consisting of orthogonal matrices with determinant 1. We can then think of Cayley transformation as a map from into its Lie group .
This map is nice because it allows us parametrise rotation matrices! Generally, if one wishes to study a Lie group, one might do that by studying its Lie algebra which behaves much nicer because we can do linear algebra stuff there.
One thing I want to mention about is that it does not require infinite processes. The formula is precise and does not require approximation. Compare this with the more commonly studied exponential map , which is also a map from a Lie algebra to its Lie group :
for . In this setting, usually the underlying field is taken to be so if one is given , one needs to take a limit (which requires infinite processes) to exactly compute . It shares a similar property with the Cayley transformation: if is skew-symmetric, then is orthogonal. In some ways, exponential map is stronger because we have things like
for example, while we don’t have an analogue for this with the Cayley transformation. What I mean by that is it’s not possible to find as a function of that satisfies
for all . Nevertheless, it does not mean that the Cayley transformation is less interesting. I feel that this map needs to be more well-studied, especially because it might provide an alternate theory of connecting Lie algebras with Lie groups more algebraically.
I will discuss a generalisation of this Cayley transform to a more general geometric setting in my next post. Roughly speaking (I will make this more rigorous in the next post), given a symmetric, non-degenerate matrix , we can define a symmetric bilinear form for all . This gives a new geometry, with the case giving the Euclidean geometry back. The matrix gives relativistic geometry.
This generalised Cayley transform depends on . We will also see that a modification of being skew-symmetric and orthogonal with respect to in the next post.
In the previous post, I introduced the notion of Dyck path and Dyck word. I also introduced the concept of tunneling in a Dyck path. We can associate to a Dyck path a permutation. I also mentioned how you can label a Dyck path (or Dyck word) using a set of letters. In this post, I will define what the multiplication map is and give some examples to illustrate this further.
Multiplication of two Dyck paths
Given two Dyck paths , we define the product of and , denoted by , as follows:
Associate to a permutation .
Pair the steps in based on its tunnel.
For , either
write u in -th position of the word of if step of has not been read before, or
write d in -th position of the word of if step of has been read.
Associate the resulting word to its Dyck path, this will be the path .
It is not obvious that the product of two Dyck paths will still yield another Dyck path. Fortunately, this is the case.
Theorem: If , then .
Proof: The resulting word of will have precisely up-steps and down-steps since there are tunnels in . Moreover, in the first position, , the number of u will never be smaller than the number of d since the only way a d in position is produced is to have the pair of step of read. Before it is read, a u must have been written at some position . Hence the resulting word is a Dyck word so the associated lattice path is a Dyck path.
Let’s have a look at a couple of examples.
Example 1. Let and be represented by uududd and uduudd, respectively. The Dyck path is associated to
so the way we read is we read the 1st step, followed by 6th, 2nd, 3rd, 5th, and 4th steps. Here are the steps to determine :
First we pair the steps in . Step 1 is paired with step 6. Step 2 is paired with step 3, and step 4 is paired with step 5.
We look at step of . Its pair, step 6, has not been read before. Hence, step 1 of is u.
We look at step of . Its pair, step 1, has been read. Hence, step 2 of is d.
We look at step of . Its pair, step 3, has not been read before. Hence, step 3 of is u.
We look at step of . Its pair, step 2, has been read. Hence, step 4 of is d.
We look at step of . Its pair, step 4, has not been read before. Hence, step 5 of is u.
Last, we look at step of . Its pair, step 5, has been read. Hence, step 6 of is d.
The resulting Dyck word is ududud, which can then be interpreted into the Dyck path of .
In other words,
Example 2. Let and be represented by uudduudd and uuududdd, respectively. The Dyck path is associated to and the steps of is paired in this manner: step 1 with step 4, step 2 with step 3, step 5 with step 8, and step 6 with step 7. The first step of is u. The second step of is again an u since the pair of step in $D_1$, which is step 3, has not been read before. The third step of is d since the pair of step , which is step 2, has been read before. Continuing this process, the remaining steps are u, d, u, d, and d. Hence,
If , we can think of this multiplication operator as a map
We will see below how multiplication works in , and .
There are only 2 Dyck paths of semilength 2, which are given below.
It can be verified that
In other words, , , , and . We can summarise the above information in a multiplication table below. The convention for is is picked from the column below , and is picked from the row to the right of .
There are 5 Dyck paths of semilength 3, which are given below.
The multiplication table is given below.
There are 14 Dyck paths of semilength 4.
Here is the multiplication table.
Have a look at any multiplication table I provided above. If you look at any column, you will find every entry in that column to be different. To say it more precisely, given a Dyck path where , if with , then . In other words, is actually a bijection!
To come to think of it, it is not entirely clear that the multiplication map is well-defined (the proof is not as simple as we would like, as you see above), let alone that it is a bijection! If it is indeed a bijection, given any , we can generate bijections at the same time!
Conjecture. For any , the map is a bijection.
In the next post, I will give an explicit algorithm to tackle the following problem: given , how do you find such that ? Note that giving such an algorithm doesn’t necessarily mean that it is a bijection. We need to say more to be entirely sure that it is a bijection.
There are several other nice observations about this multiplication, just by looking at the table above. But I think it deserves to be put as a single post, later 🙂
In this series of posts, I will try to introduce a family of mappings between Dyck paths of the same length. The map itself can be thought of as multiplication of two Dyck paths. In this first part, I will lay out all the ingredients needed in order for us to define properly what it means here to multiply two Dyck paths. In the second part, I will define the multiplication map and give some concrete examples. In the third part, I will give a map to reverse the multiplication map we will see in the second post. This is an attempt to show that the family of mappings is indeed a family of bijections between Dyck paths. In the last part, I will highlight several interesting properties about this multiplication map: I have a proof for some observations, but mostly I will be giving some open questions.
Dyck paths and Dyck words
A Dyck path of length (or of semilength ) is a lattice path which starts at and ends at which does not cross above the diagonal line (but if it touches the line, it’s okay).
Another interpretation for , one which I will use throughout this series of posts, is as a path from that ends at which consists of a series of up-steps and down-steps such that it never goes below the -axis.
Let be the set of all Dyck paths of length . It is well-known that
the th Catalan number. This gives a combinatorial interpretation of the Catalan numbers in terms of Dyck paths.
Now, given a Dyck path, we can associate to it its Dyck word, which is just the way we read the path from left to right, consisting of a string of us (for up-steps) and ds (for down-steps). Denote by the set of all Dyck words of length . Throughout this post, the terms Dyck path and Dyck word will be interchangeable, unless distinction is required. In other words, most of the times we will make no distinction between the set and .
Below is an example of a Dyck path in . We can encode this Dyck path into uuduuddd.
There are only Dyck paths of semilength 2, which are
Below we see the Dyck paths of semilength 4:
which, as you can see, are in total.
Note that if a Dyck word is given, for any , in the first subword, the number of u must not exceed the number of d, for otherwise the Dyck path will cross below the -axis. It is also obvious that the number of u and d in any Dyck word of length must both be equal to .
Dyck path tunneling
Given a Dyck path , define a tunnel in to be the horizontal segment between two lattice points of that intersects only in these two points and stays always below . If , then has exactly tunnels and each tunnel can be associated with a pair of (u,d) such that the u step and the d step are connected by a tunnel. In the Dyck path in Figure 1 above, we have 4 tunnels: those connecting with , with , with , and with . See all the tunnels in red dashed line below.
Given a Dyck path , a step is called the conjugate of step if there is a tunnel connecting step and step of . If step is the conjugate of step , we write . Note that the conjugation map is an involution, i.e. for all . In the Dyck path above, for example, , , , and .
Associating to a Dyck path a permutation
Let be the set of permutation of elements in the set . Given a Dyck path , we can associate to it a permutation via the following rules:
Read the Dyck word of from left to right.
If the k-th u from this Dyck word falls in position , then define , where .
If the k-th d from this Dyck word falls in position , then define , where .
This association gives an injective map from to . To give an illustration, the Dyck path in Figure 1 above corresponds to
Now observe that for any Dyck path that is associated with , it is necessary that (resp. ) because the first (resp. last) step in any Dyck path is always an up-step (resp. a down-step).
Labeling a Dyck path
Let a Dyck path be given. We can associate to it a string of length consisting of letters , each appearing exactly twice, via the following rules:
Pair the steps and so that they are connected by a tunnel.
Label the -th and -th position of this string with one out of letters .
Once a letter has been used, it cannot be used anymore.
It is important to note that the order for choosing the letters to use does not matter. For example, the Dyck path in Figure 1 corresponds to , but it can also correspond to . What does matter is the position of the letters.
Now that we have all the stuff we need to know, I will define the multiplication map in the next post.
In 1874, a French and Belgian mathematician Eugène Catalan introduced the numbers
now better known as super Catalan numbers, and stated that the numbers are integers. The entire text of his note in French, an item in a column called Questions which appeared in Nouvelles Annales de Mathématiques Volume 13, is as follows:
étant deux nombres entiers quelconques, la fraction
est égale à un nombre entier.
Unfortunately, there is also another sequence of numbers which goes by the name of super Catalan numbers too, called the Schröder-Hipparchus numbers. It makes the naming a bit ambiguous.
Nevertheless, can be viewed as a generalization of the famous Catalan numbers
because You can see the Catalan sequence here in Online Encyclopedia of Integer Sequences (OEIS).
You can prove that is always an integer for any non-negative integers and by observing that satisfies
and that is the central binomial coefficient , where we can proceed by induction on . Except for , is always even so sometimes is considered.
Unlike the Catalan numbers which so far have more than 200 combinatorial interpretations (Richard Stanley gave 66 interpretations in his book Enumerative Combinatorics 2, and he added some more as an addendum), you might be surprised to know that up to date, there is no known combinatorial interpretation of . However, there are some combinatorial interpretations of the specific case of super Catalan numbers in terms of pairs of Dyck paths with restricted height (see a paper by Gessel, for instance), cubic plane trees (see a paper by Pippenger and Schleich), or restricted lattice paths (see this paper by Chen and Wang). The first two papers give a combinatorial interpretation for and the last one gives a combinatorial interpretation for where .
There are also weighted interpretations of super Catalan numbers in terms of Krawtchouk polynomials in this paper by Georgiadis, Munemasa, and Tanaka. The most recent work on super Catalan numbers is due to Allen and Gheorghiciuc, who provided a weighted interpretation in terms of positive and negative 2-Motzkin paths in their paper here.
My current research is closely connected to super Catalan numbers, but not in a combinatorial flavor. However, I was curious why people haven’t been able to interpret these seemingly harmless numbers as a counting problem. To do that, I decided to do a bit of detour: I wandered around in the realm of combinatorics. Since one of the interpretations of the Catalan numbers is in terms of Dyck paths, I decided to start with Dyck paths.
To those who are not familiar, a Dyck path of length is a lattice path, starting at and ending at , that consists of up-steps and down-steps and never goes below the -axis. You could also think of Dyck paths of length as such paths starting from to that lies below (but may touch) the diagonal line . The number of Dyck paths of length is the th Catalan number . You can see some illustrations here.
It thus makes sense to find a combinatorial interpretation of super Catalan numbers in terms of Dyck paths, hoping that the description of relies solely on Dyck paths, only perhaps in more intricate detail. In order to come up with an interpretation, all I need to do is to find a very specific bijection between two Dyck paths that should work in general. That turns out to be a very difficult thing to do. I played with many bijections but none seemed to work. I ended up finding a curious family of bijections between Dyck paths of the same length, though. But more on that later, in another post.
So the moral of the story is you can wish to solve something, but you may end up getting something else. If you are lucky (or unlucky, depends on how you interpret it), that ‘something else’ might just be another question waiting to be discovered 😛