Editing Adjacency matrix (section)

==Definition==
For a simple graph with vertex set {{math|''U'' {{=}} {''u''<sub>1</sub>, ..., ''u''<sub>''n''</sub>}<nowiki/>}}, the adjacency matrix is a square {{math|''n'' × ''n''}} matrix {{mvar|A}} such that its element {{mvar|A<sub>ij</sub>}} is 1 when there is an edge from vertex {{math|''u''<sub>i</sub>}} to vertex {{math|''u''<sub>j</sub>}}, and 0 when there is no edge.<ref>{{citation| title=Algebraic Graph Theory| edition=2nd| first=Norman|last=Biggs|series=Cambridge Mathematical Library|publisher=Cambridge University Press|year=1993|at=Definition 2.1, p.&nbsp;7}}.</ref> The diagonal elements of the matrix are all 0, since edges from a vertex to itself ([[Loop (graph theory)|loops]]) are not allowed in simple graphs. It is also sometimes useful in [[algebraic graph theory]] to replace the nonzero elements with algebraic variables.<ref>{{citation|last=Harary|first=Frank|author-link=Frank Harary|journal=SIAM Review|mr=0144330|pages=202–210|title=The determinant of the adjacency matrix of a graph|volume=4|issue=3|year=1962|doi=10.1137/1004057|bibcode = 1962SIAMR...4..202H}}.</ref> The same concept can be extended to [[multigraph]]s and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements. Loops may be counted either once (as a single edge) or twice (as two vertex-edge incidences), as long as a consistent convention is followed. Undirected graphs often use the latter convention of counting loops twice, whereas directed graphs typically use the former convention.

===Of a bipartite graph===
<!-- [[Adjacency matrix of a bipartite graph]] & [[Biadjacency matrix]] redirect here -->
The adjacency matrix {{mvar|A}} of a [[bipartite graph]] whose two parts have {{mvar|r}} and {{mvar|s}} vertices can be written in the form 
: <math>A = \begin{pmatrix} 0_{r,r} & B \\ B^\mathsf{T} & 0_{s,s} \end{pmatrix},</math>
where {{mvar|B}} is an {{math|''r'' × ''s''}} matrix, and {{math|0<sub>''r'',''r''</sub>}} and {{math|0<sub>''s'',''s''</sub>}} represent the {{math|''r'' × ''r''}} and {{math|''s'' × ''s''}} [[zero matrix|zero matrices]]. In this case, the smaller matrix {{mvar|B}} uniquely represents the graph, and the remaining parts of {{mvar|A}} can be discarded as redundant. {{mvar|B}} is sometimes called the ''biadjacency matrix''.

Formally, let {{math|''G'' {{=}} (''U'', ''V'', ''E'')}} be a [[bipartite graph]] with parts {{math|''U'' {{=}} {''u''<sub>1</sub>, ..., ''u''<sub>''r''</sub>}<nowiki/>}}, {{math|''V'' {{=}} {''v''<sub>1</sub>, ..., ''v''<sub>''s''</sub>}<nowiki/>}} and edges {{mvar|E}}. The biadjacency matrix is the {{math|''r'' × ''s''}} 0–1 matrix {{mvar|B}} in which {{math|''b''<sub>''i'',''j''</sub> {{=}} 1}} [[if and only if]] {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>) ∈ ''E''}}.

If {{mvar|G}} is a bipartite [[multigraph]] or [[weighted graph]], then the elements {{mvar|b''<sub>i,j</sub>''}} are taken to be the number of edges between the vertices or the weight of the edge {{math|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>)}}, respectively.

===Variations===
An {{nowrap|{{math|(''a'', ''b'', ''c'')}}}}-adjacency matrix {{mvar|A}} of a simple graph has {{math|''A''<sub>''i'',''j''</sub> {{=}} ''a''}} if {{math|(''i'', ''j'')}} is an edge, {{mvar|b}} if it is not, and {{mvar|c}} on the diagonal. The [[Seidel adjacency matrix]] is a {{math|{{nowrap|(−1, 1, 0)}}}}-adjacency matrix. This matrix is used in studying [[strongly regular graph]]s and [[two-graph]]s.<ref>{{cite journal |last=Seidel |first=J. J. |title=Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3 |journal=[[Linear Algebra and Its Applications|Lin. Alg. Appl.]] |volume=1 |issue=2 |pages=281–298 |year=1968 |doi=10.1016/0024-3795(68)90008-6 |doi-access= }}</ref>

The '''[[distance matrix]]''' has in position {{math|(''i'', ''j'')}} the distance between vertices {{mvar|v<sub>i</sub>}} and {{mvar|v<sub>j</sub>}}. The distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, but instead of telling only whether or not two vertices are connected (i.e., the connection matrix, which contains [[Boolean algebra|Boolean values]]), it gives the exact distance between them.