Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here

I have to find the inverse matrix of this matrix that represents a relation. My question is, is it possible to use elementary row operations on a one-zero matrix to find the inverse? I've done it several times already, and I doesn't seem to work for me.

I have another question, regarding this same matrix. Instead of finding $R^-1$, I have to find $R^2$ I am not certain on how to square a relation. I already tried re-reading my textbook, but I didn't really find anything useful on that matter. Could someone please help?

Thank you!

share|cite|improve this question
up vote 3 down vote accepted

Suppose we have a relation $R$ on $\{1,2\}$, such that we have $1R1$, $1R2$, but not $2R1$ nor $2R2$. In another words, we have $R=\{(1,1),(1,2)\}$. We can represent this relation as a matrix $M_R$ as


For the inverse of this relation $R$, namely $R^{-1}$, we have $1R^{-1}1$ and $2R^{-1}1$, since $xRy$ if and only if $yR^{-1}x$. That is, $R^{-1}=\{(1,1),(2,1)\}$. The matrix representation of $R^{-1}$ would then be


Note that $M_R$ and $M_{R^{-1}}$ are not matrix inverse of each other in the matrix multiplicaitve sense. That is, you are not actually looking for a matrix $M_{R^{-1}}$ such that $M_{R^{-1}} M_R =I$. (In general, such a matrix describing a relation need not be invertible at all!) So row reduction is out of the table. But curiously, they are indeed related by another familiar matrix operation.

To give you a hint, often binary inverse relations are called transpose relations.

(By the way, do you know how these matrix representations of relations are constructed?)

share|cite|improve this answer
To add, one can think of adjoints (transposes) as "conceptual inverses" with respect to a relation, as nicely explained by omar in this answer. – Nick Alger Nov 5 '12 at 16:31

What you want is not the inverse of the matrix $M_R$, but rather the matrix of the inverse relation $R^{-1}$: you want $M_{R^{-1}}$, not $(M_R)^{-1}$. Elementary row operations are one way of computing$(M_R)^{-1}$, when it exists, they won’t give you $M_{R^{-1}}$.

Note also that while $(M_R)^{-1}$ doesn’t always exist: The relation $R=\{\langle 1,2\rangle\}$ on $\{1,2\}$ has the matrix $$M_R=\begin{bmatrix}0&1\\0&0\end{bmatrix}\;,$$ and you can easily check that this $M_R$ is not invertible in the linear algebra sense.

Every relation, however, has an inverse relation, so for any relation $R$, $M_{R^{-1}}$ exists. Recall that if $R$ is a relation on $A$, $$R^{-1}=\Big\{\langle y,x\rangle\in A\times A:\langle x,y\rangle\in R\Big\}\;:$$ it’s the relation that you get from $R$ by ‘turning all the ordered pairs around’. This operation actually does have an effect on the matrix that is familiar from linear algebra, but it’s not taking the inverse of the matrix: it’s taking the transpose. For example, if $R=\{\langle 1,2\rangle\}$ on $\{1,2\}$, $R^{-1}=\{\langle 2,1\rangle\}$, and


For any relation $R$, the rows of $M_R$ correspond to the first components of the ordered pairs in $R$, and the columns of $M_R$ correspond to the second components. When you turn the pairs around to form $R^{-1}$, you interchange the first and second components, and this has the effect of interchanging the rows and columns of the matrix. But that’s exactly what transposing does, so you automatically get $M_{R^{-1}}=M_R^T$.

This is nice, actually, since it’s easier to find the transpose of a matrix than it is to find the inverse, even when it exists!

share|cite|improve this answer
@bonsoon: So, I took the inverse of the relation, and then represented that as a matrix: I got the exact same matrix, does that mean the relation is symmetric? – Mack Nov 5 '12 at 18:49
@EMACK: Yes, it does. $R$ is symmetric if and only if $R=R^{-1}$, which is the case if and only if $M_R=M_R^T$: the relation is symmetric if and only if its matrix is symmetric. – Brian M. Scott Nov 5 '12 at 18:59
I don't intend to be bothersome, but I edited my post by adding another question; and I was wondering, should I have started a new thread? Do other users get a notification that I edited my post? – Mack Nov 6 '12 at 13:18
@EMACK: No, they don’t, and it would have been better to ask a new question. However, I can give a short answer: in this case it’s just the ordinary square by matrix multiplication. I think that I recently wrote something about that in another answer; if I can find it, I’ll post a link. – Brian M. Scott Nov 6 '12 at 13:40
@EMACK: Found it: it’s an answer to one of your earlier questions. – Brian M. Scott Nov 6 '12 at 13:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.