Skip to main content

Authors in a Markov matrix: Which author do people find most inspiring? (7)


The adjacency matrix

A matrix is a two-dimensional rectangular array of numbers arranged in rows and columns. It looks like a table of numbers. The readers who want to more about matrix, see the Appendix A (will be shown up the later blog) in this document as a short introduction, or to know more deeply, see [7].

I would like to show how a matrix can be used to describe a graph. My motivation is to be able to write down a graph. Following some rules, we can write down a graph in matrix form. Let me introduce such a method for representing a graph here. The matrix I will describe is called an adjacency matrix.

Definition: An adjacency matrix \(A\) of a graph of \(N\) vertices is an \(N \times N\) matrix where the element \(a_{i,j}\) is 1 when there is a directed edge from node \(i\) of the graph to node \(j\), otherwise 0.

That's all there is to it. An element in an adjacency matrix that represents a connection is a 1; an element that represents the lack of a connection is a 0.  Let me show you some examples.

First, let's think about how we could represent relationships between people as a graph. A graph edge will represent that one person likes another person. I've decided to have an edge when someone likes someone else. It would be possible for an edge to mean that two people dislike each other, but I would prefer to know more about who likes whom.  A note here, however --- a definition like the one I am making for my graph depends on me, the person who is solving the problem. I can define any meaning for a graph as long as there is no contradiction. This is not based on facts, but on what I have defined, so we first need to agree with this idea.  If I say ``define,'' ``assume,'' or ``let us think...'', I am asking you to agree. If you don't agree with these initial definitions, then the rest of the discussion is meaningless!

Next time I will introduce Alice and draw a like-not-like graph.

References

[7] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition,'' Wellesley-Cambridge Press, 2009

Labels:

Comments

Post a Comment

Popular posts from this blog

Why A^{T}A is invertible? (2) Linear Algebra

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the null spa
Post a Comment
Read more

Gauss's quote for positive, negative, and imaginary number

Recently I watched the following great videos about imaginary numbers by Welch Labs. https://youtu.be/T647CGsuOVU?list=PLiaHhY2iBX9g6KIvZ_703G3KJXapKkNaF I like this article about naming of math by Kalid Azad. https://betterexplained.com/articles/learning-tip-idea-name/ Both articles mentioned about Gauss, who suggested to use other names of positive, negative, and imaginary numbers. Gauss wrote these names are wrong and that is one of the reason people didn't get why negative times negative is positive, or, pure positive imaginary times pure positive imaginary is negative real number. I made a few videos about explaining why -1 * -1 = +1, too. Explanation: why -1 * -1 = +1 by pattern https://youtu.be/uD7JRdAzKP8 Explanation: why -1 * -1 = +1 by climbing a mountain https://youtu.be/uD7JRdAzKP8 But actually Gauss's insight is much powerful. The original is in the Gauß, Werke, Bd. 2, S. 178 . Hätte man +1, -1, √-1) nicht positiv, negative, imaginäre (oder gar um
Post a Comment
Read more

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) . 
Post a Comment
Read more