Problem solving and mindfulness

I wanted to write a little something about a change I noticed in the way I usually respond when I find myself unable to find a solution to a problem. A few weeks ago I was trying to solve this problem

After working on it off and on for a few days, I hit upon the key idea that solved it just as I was falling asleep.

I don’t think it’s a very tough problem, however I had quite some trouble cracking it. Luckily there was a hint, and I was able to make some progress, but I got stuck soon after. I started to feel a familiar sense of frustration and a strong desire to give up and look the solution up. In the not so very distant past, I would have succumbed and looked the solution up, and then immediately felt insecure about it.

This time, I told myself that I should put it away for the day and give it another shot later. I started working on it again the next day, when a different approach suggested itself and I was able to go a little further. This surprised me because my usual practice is to try the same thing over and over again and then get frustrated when it doesn’t work. Eventually, when the intrusive thoughts, “It’s hopeless”, “I told you, you’re horrible at math”, “stop fooling yourself”, inevitably won, I would give up and be depressed for a while.

Recently however, I am noticing that I have been able to avoid this mental road block. It’s not that the thoughts aren’t there, they are ever present, but I’ve been getting better at keeping at it even with the circling negativity. I have observed that if I acknowledge the negative thought (or just ignore it) and try again, more often than not, I find the solution to the problem, or I think of a different approach to finding it. It almost feels like the I had the answer all along, but I couldn’t find it because of all the cacophony in my head. But if I take a moment to relax, maybe do the 4x4 breaths technique, I find the way forward.

Another factor is the complete lack of time pressure. I have no assignment deadlines, or timed exams where I have to solve problems in a finite amount of time. I’m doing this as a hobby, and I can take all the time I need. Without all the anxiety to finish in time, it’s a lot easier to think of alternative approaches to problem solving. Sure, sometimes I feel insecure about spending whole days to solve a relatively simple problem, but hey, instead of giving up and feeling sad about it, I’m finding answers and feeling a sense of joy and accomplishment.

Powers of a permutation matrix - Part 3

In Part 2, we saw how permutations consisting of simple cycles always return to their original configurations. Now let’s consider a permutation p, consisting of m number of cycles, with sizes k₁, k₂, … k_m, such that

and no two cycles are of the same length. For such a permutation we have

since any cycle will return to it’s original position at the q times kth application of p (where k is the length of the cycle), which means that all cycles in the permutation will return to their original positions when the permutation is applied

times.

But what if the cycles are not all of the cycles are of different lengths? In that case we only need to consider the unique lengths among the various cycle lengths. That is, if the permutation consists of one 2-cycle, three 5-cycles, two 3-cycles, and two 7-cycles, then the permutation will return to it’s initial configuration at the 2 x 5 x 7 x 3 = 210th application of the permutation. This is easy to see becuase if there are l cycles of length k, all of them will return to their starting configuration at every kth application of the permutation. Once again I’m ignoring situations where one cycle is a of a length that is a multiple of another cycles length, since the other cycle will in any case return to it’s original position when the larger cycle returns to it’s original position. The thing it would impact is the smallest number N such that p^N = e. I’m not sure how to go about tackling that.

One question remains - Can all permutations be represented as collections of cycles. To see why the answer is yes, consider that any permutation has at least one cycle. Let’s assume that a permutationhas m cycles, with fixed points being cycles of length 1. Now imagine that there are some elements in the set being permuted that do not belong to either of the m cycles. If we now apply the permutation to just these points, then either they retain their positions, making them fixed points which is a contradiction, or they do move to different positions, implying that there is a cycle of size at least two, which is also a contradiction. This means that every permutation has to be composed of cycles.

One last note - I posted about powers of permutations on reddit, and a user asked if anything can be said about p^n! where n is the number of elements being permuted. Since the lengths of the cycles that make up any permutation will always be lesser than or equal to the number of elements in the set, n! will include all the cycle lengths in the product. So p^n! will also be the identity. So there was a much simpler way to show that such a number exists. But it is not necessarily the smallest number such that p^N is the identity. I am fairly confident that the smallest number N with this property is the least common multiple of (n, n-1, n-2, …, 1) but I don’t know how to prove it.

Order of the Power Set

Here are two ways to determine the number of elements in the Power set of a finite set of objects. The set of all subsets of a set is called a power set, and the number of all the elements in a given set is called its order. Consider the following set S = {a, b, c}. The order of this set is 3, and its power set is P(S) = {O, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, S}. Notice that the power set contains all subsets of S, including S, and the empty set O. We can see that P(S) has 8 elements, so its order is 8. If you carried out a similar exercize for a set S’ = {a, b, c, d}, we will find that its order is 16. It looks like the order of a the power set of a set with n elements is 2ⁿ.

We can show that this is actually true. Let’s prove it in two ways. First let’s use mathematical induction, which is intuitive and clean, but a little dry IMO. Next, let’s show that it is true by just counting the elements (kind of). This is a lot more fun, and it’s nice to see how a couple of things come together to solve the problem.

But first let’s do induction. Notice that if a set S is empty, it has n = 0 elements. The power set, P(S), then only has one element - the empty set (which is also the entire set S). So the order of the power set is 1, and 2⁰ = 1, so the base case is true. Now let’s assume that it is true for the power set of a set with n elements. So the power set of a set with n elements would have order 2ⁿ. Let’s denote the elements of the power sets as S₁, S₂, …, S_m, where m = 2ⁿ. Now consider adding one more element to S, bringing the number of elements contained by it to n+1. Adding this additional element to S creates a whole bunch of new subsets, and we have to determine how many new subsets are created and add it to 2ⁿ, to find the order of the new power set of S. Notice that all the new subsets of S can be created by adding the new element to each of the subsets of S with n elements.

For example, if S = {a, b}, then P(S) = {O, {a}, {b}, S}. If we add a third element, c, to this set, then we get the new subsets -

Essentially, by adding an additional element to S, we are adding one additional subset to every subset in power set of the original set. So we have two times as many elements in the power set of a set with n+1 elements, as in the power set of one with n elements. That is, the order of the power set of a set with n+1 elements is 2 x 2ⁿ = 2ⁿ⁺¹, and we are done.

Now let’s do it the fun way. Notice that we can determine the number of subsets of a set with n elements by counting the number of subsets with 0 elements (the empty set), the number of subsets with 1 element (these are called singletons, there are n of them), with 2 elements and so on, up to the number of subsets with n elements (there’s one such subset - the entire set), and then adding them all up. To do this, let’s find the number of subsets with k elements. This is equivalent to the number of ways of choosing k objects from a collection of n objects. We know that this is

Now we have to sum the number of subsets with k elements from k = 0 to k = n. That is, the order of the power set is

All that is left to do is to evaluate this sum. It looks a little intimidating, and trying to evaluate it by expanding the sum and adding all the terms will turn out to be quite an effort. So maybe there’s another way. Notice that the sum looks remarkably similar to the sum in the binomial theorem:

In fact if we set x = y = 1 in the binomial theorem, the sum will be the same as the sum in our expression for the order of the power set,

and

which means

and we’re done!