Talk:Adjacency matrix

Untitled

I removed

The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.

from the article. The edges in graphs are defined as a set, so it is not possible that an edge (v_i,v_j) is contained more than once. I think the adjacency matrix should be a (0,1)-matrix and perhaps in a subsection someone could extend this definition to count the number of edges two vertices share.MathMartin 18:56, 25 Sep 2004 (UTC)

This is correct, although multigraphs have a multiset of edges. Derrick Coetzee 00:25, 2 Oct 2004 (UTC)

Maybe the example graph can contain a self loop, to show how it can be represented into the adjacency matrix.

That's a great idea. Deco 01:39, 21 Mar 2005 (UTC)

Most software packages show a binary adjacency matrix, even on the diagonal. But loops are always counted twice, and some books show an adjacency matrix like this one, with 2 on the diagonal...

I don't think the information about the relationship between the invertibility of I-A and the presence of directed cycles in the graph is correct. For example, if the adjacency matrix of a directed graph is like the one below, the graph both contains a cycle and has invertible I-A.

${\begin{pmatrix}0&1&0&1\\0&0&1&1\\1&0&0&0\\1&1&0&0\\\end{pmatrix}}.$

The statement about det(I-A) is definitely wrong. For an infinite set of counter-examples, consider the adjacency matrices of complete graphs of 3 or more vertices. They all have determinant I-A not equal to 0, so are invertible, but they also all contain cycles, whether treated as directed or undirected graphs. Cdsmith (talk) 15:31, 1 May 2008 (UTC)

Properties section

What does one cannot 'hear' the shape of a graph mean? --Bkkbrad 19:53, 16 November 2006 (UTC)

See the following articles -

• Hearing the shape of a drum
• Spectral graph theory
• Isospectral

Hope that helps. It's all a little out of my league. Perhaps it needs citation, though, because it is not obvious to laymen. Also, there is at least one article on arXiv claiming you can hear the shape of certain graphs. [1] --W0lfie (talk) 16:57, 18 December 2007 (UTC)

Relative to the Adjacency Matrix example, for those less familiar with this area a small edit would clarify that the matrix listing refers to nodes 1 to 6 in the picture, with node 1 at the top and node 6 at the bottom of the matrix --TopoRubin 16:06, 3 March 2007 (UTC)

Is the Adjacency Matrix correct? It appears to indicate that node 1 is adjecent to itself. - I am not a mathematician, but unless there is a requirement in a closed sytem for this to be so I suggest the first entry should be a '0', thus maintaining the diagonal of non-self-adjacency. —Preceding unsigned comment added by 82.69.206.96 (talk) 23:57, 5 July 2008 (UTC) In general there is no restriction on self-adjacency. An example would be a no-op in a state machine. 129.11.146.164 (talk) 14:44, 18 November 2008 (UTC)

What does $d$ mean in the Spectrum section? My guess is it's the largest eigenvalue; but then the formula for spectral radius $\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|$ does agree with the usual definition of spectral radius. Thatsme314 (talk) 18:30, 16 August 2018 (UTC)

History section

Could someone with the necessary references start a history section? First known use of adjacency matrices, etc. I've searched around online and can't find anything on it's first known/documented use, or which specific cultures used it. Mojodaddy (talk) 14:23, 17 May 2009 (UTC)

one-hop connectivity matrix?

I don't know if it's right, but I added the name 'one-hop connectivity matrix' for adjacency matrix. I'm not sure, but this might be only used in network communication (ie, IEEE) circles. Rhetth (talk) 00:11, 8 December 2009 (UTC)

Adjusting "directed graph" section to address discrepancies in interdisciplinary research

@Wcherowi: Adjacency matrices are a central concept in all applications of network science. In network science, it is standard to define adjacency matrices of directed graphs such that a_{ij}=1 indicates an edge from j to i. This is relevant for dynamical systems, where \dot x = Ax describes a simple and widely studied model for the spread of information, disease, etc. I think this info should be included in this section, so I am proposing the following version:

The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that

1. a non-zero element A_ij indicates an edge from i to j or
2. it indicates an edge from j to i.

The former definition is commonly used in graph theory. The latter is common in most applied sciences (e.g., dynamical systems, physics, network science) where A is sometimes used to describe linear dynamics on graphs .

Using the the first definition, the in-degrees of a vertex can be computed by summing the entries of the corresponding column and the out-degree of vertex by summing the entries of the corresponding row. When using the second definition, the in-degree of a vertex is given by the corresponding row sum and the out-degree is given by the corresponding column sum.

Labeled graph	Adjacency matrix
Directed Cayley graph of S4	Coordinates are 0–23. As the graph is directed, the matrix is not necessarily symmetric.

Aliceschwarze (talk) 04:34, 19 June 2020 (UTC)

This certainly needs to be addressed one way or another. Consider the Stochastic matrix article, which directly addresses the existence of multiple conventions and explicitly states the one chosen. (It corresponds to the i,j convention here, unless I am mistaken, but it makes the choice explicit.) The same should happen here, and the proposed edit seems excellent to me. Solemnavalanche (talk) 12:07, 19 June 2020 (UTC)

After checking the reference I took the liberty of inserting it -- it's an important addition. Thanks @Aliceschwarze. Solemnavalanche (talk) 12:27, 19 June 2020 (UTC)

I also think this is a good addition. I was going to suggest something like this in any event. --Bill Cherowitzo (talk) 17:10, 19 June 2020 (UTC)

How about moving the discussion of the two conventions to the "Definition" subsection? (The "A_ij = 1 <=> edge from i->j" convention is established earlier in this subsection: "such that its element Aij is one when there is an edge from vertex i to vertex j, and zero when there is no edge.") The current discussion seems out of place where it is. As is typical in expository math, it seems easiest to fix a convention and then use it throughout the article while also acknowledging that other conventions exist. Horacelamb (talk) 19:50, 19 June 2020 (UTC)

References