Transitive Closure

The closure of a binary relation R on a set A, with respect to a property (reflexivity, symmetry, transitivity) is a relation which meets the following three criteria.

1. The relation contains R.
2. The relation possesses the property.
3. The relation has the fewest number of ordered pairs that satisfies both criteria listed above.

The reflexive closure of R is given by \( R \cup \left \{(x,x): x \epsilon A\right \}\).
The symmetric closure of R is given by \( R \cup \left \{(y,x): (x,y) \epsilon A\right \}\).


Finding transitive closure is not as simple. Consider the relation \(R = \left \{(1,2), (3,1), (1,4), (4,3)\right \}\). We may be tempted to think that the transitive closure is given by \(R \left \{(3,2), (3,4), (1,3), (4,1)\right \}\). This new relation satisfies property 1 above but does it satisfy 2? No, it is missing (1,1), (3,3) and so on.

One method to find the transitive closure is to use Warshall's algorithm. Given a relation R on set A (which has n members), Warshall's algorithm takes as input the n x n 0-1 matrix representing R,  \(M_{R}\), and outputs a matrix representing the transitive closure of R,  \(M_{R^{*}}\).

Warshall's Algorithm:

\(for \ k = 1\  to\  n\)
    \(for\  i = 1\  to\  n\)
        \(for\  j = 1\  to\  n\)
            \(w_{ij} = w_{ij} \vee (w_{ik} \wedge w_{kj})\)

Examining the innermost loop we note that only j (which represents our columns in our matrix) is changing. The counters i and k remain constant. 

If \(w_{ik}\) is 0 then the row remains unchanged since  \(w_{ik} \wedge w_{kj}\) evaluates to 0.

If \(w_{ik}\) is 1 then \(w_{ij}\) takes the value of \(w_{ij} \vee w_{kj}\). If \(w_{ij}\) is 1 it stays as 1. If \(w_{kj}\) is 1 then \(w_{ij}\) is updated to 1. In other words we replace the \(i^{th}\) row with the result of boolean addition of the \(i^{th}\) and \(k^{th}\) rows.

Let's look at an example. Let's find the transitive closure of R={(1,1), (1,3), (2,1), (3,2)} using Warshall's algorithm.

\(M_{R} =\begin{bmatrix} 1  &0 &1 \\1  &0 &0 \\ 0  &1 &0\end{bmatrix}\)

\(k = 1: W_{1} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 0  &1 &0\end{bmatrix}\)

\(k = 2: W_{2} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

\(k = 3: W_{3} = \begin{bmatrix} 1  &1 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

So, \(M_{R^{*}}\) = {(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), (3,3)}

Would you want to work with you?

At the start of every semester I like to ask my students why are they in this class or why have they enrolled in this particular programme. Popular responses include meeting some parental demand to pursue higher education, meeting some contractual obligation to an existing employer, needing a degree to get a job. Not very many students respond that it is a path towards their chosen career. Your reasons for pursuing higher education influence your approach to your studies and ultimately the type of work ethic you develop that you take with you into industry. Even if you're not enthusiastic about your field, people should be enthusiastic to work with you.

It's natural to be motivated when you are passionate about your field and excited to join industry as a <insert job role here> but not everyone embarks on a course of study knowing what type of professional roles exist in the field and which of those roles appeal to them. If you're lucky you may find yourself in a programme that exposes you to opportunities to learn about career options and will interact with instructors who get you excited about the field thereby changing your outlook. You may even research your career options on your own and discover roles that appeal to you. But if this enthusiasm never develops the danger is that you will not reap the full benefits of your programme and habits will develop that you will likely take with you into industry.

You may begin to focus on graduation as though it is the final goal and forget that there is life after. You need to remain mindful that the student you are today will likely dictate the worker you will be tomorrow. Examine yourself and your work ethic often. Are you focused on simply finishing or excelling? Do you strive to meet deadlines or consistently seek extensions? For group work, do you do your fair share and in a timely manner or do others dread working with you? Do you wait for answers or do you seek them? You may not be passionate about your field but you should strive to be praiseworthy.

After this programme you will be employed and you will be expected to deliver in whatever role you have. Be mindful of the person you are becoming. Who do you want to be...or rather, who would you like to work with?