I have decided to take up this Exportober challenge by Prof. Neeldhara Misra primarily because I have been procrastinating on a lot of things these days and I never seem to get out of the wretched rabbit hole. I realized that this is largely due to me wanting things to be perfect - I'll do an activity X only when I have the best clarity on how to do it. Even if one assumes that there exists such a thing as best clarity on something, I repeatedly fail to realize that the time spent to attain that clarity can be minimized if I am willing to put myself out there and be imperfect.

I have been wanting to revise some linear algebra stuff that I have learned a few years ago and figure out the gaps in my understanding. Now seems like the perfect time to do that. This will be a series of posts on Matrix Factorization.

Audience: The intended audience for this blog post is anybody who has done high school math - which means I might talk about things that are rather standard to you (I hate to use the word trivial). So, feel free to skip through such sections. (Hopefully, I adhere to this promise and don't assume things just because I happen to know them).

We have been factorizing various objects since eternity. For example, the prime factorization of $x = 202419000$ is

We wrote this large composite number as a product of prime numbers. How is this helpful? Say we have another large number $y = 35054208 = 2^7 * 3^5 * 7^2 * 23$ and we want to write the simplest form of the fraction $\frac{y}{x}$, i.e., the greatest common divisor of the numerator and denominator should be $1$. This problem is rather simple if we are given $x$ and $y$ as a product of prime factors instead of a large composite number.

Sure, we could still argue that if we know the $gcd(x,y)$ we can obtain the simplest form by dividing both the numerator and denominator by $gcd(x,y)$. Hence it is not really necessary to compute the prime factorization of $y$ and $x$. But there are problems where we really need to be able to factorize large composite numbers. Say you are working for an agency that asks you to monitor the conversation between two parties $A$ and $B$. The two parties have agreed upon a large secret prime number $y$ which you are unaware of. Suppose $A$ wants to communicate some message $x$ (which again turns out to be a large prime number). $A$ is not naive enough to send $x$ directly to $B$, else you would have intercepted the message easily. Instead, $A$ sends the product $(y \cdot x)$. Since $B$ has $y$, it can easily recover $x$ from this product. On the other hand, you can retrieve this conversation only if you are able to factorize $(y\cdot x)$.

Consider a number $x = p_1^{n_1} \cdot p_2^{n_2} \cdot \ldots \cdot p_k^{n_k}$ where $p_i$'s are prime numbers. Let us write the prime factorization $P_x$ of $x$ as follows:

For the prime factorization problem, we could ask the following questions:

The answer to the first two questions is yes due to the Fundamental Theorem of Arithmetic. To avoid digression from the main topic, I will not go into the third question. But the point is, similar questions can be asked for any factorization problem.

Before starting matrix factorization, I will walk through some basic definitions of vectors, matrices, and other related terminologies in the next post. See you soon!!