# Linear Algebra

*Graphs.jl* provides the following matrix operations on both directed and undirected graphs in the `LinAlg`

submodule:

`Graphs.LinAlg.Adjacency`

`Graphs.LinAlg.AveragingAdjacency`

`Graphs.LinAlg.AveragingLaplacian`

`Graphs.LinAlg.CombinatorialAdjacency`

`Graphs.LinAlg.GraphMatrix`

`Graphs.LinAlg.Noop`

`Graphs.LinAlg.NormalizedAdjacency`

`Graphs.LinAlg.NormalizedLaplacian`

`Graphs.LinAlg.StochasticAdjacency`

`Graphs.LinAlg.StochasticLaplacian`

`Graphs.LinAlg.adjacency_matrix`

`Graphs.LinAlg.adjacency_spectrum`

`Graphs.LinAlg.degrees`

`Graphs.LinAlg.degrees`

`Graphs.LinAlg.incidence_matrix`

`Graphs.LinAlg.laplacian_matrix`

`Graphs.LinAlg.laplacian_spectrum`

`Graphs.LinAlg.spectral_distance`

`Graphs.LinAlg.symmetrize`

`Graphs.LinAlg.symmetrize`

## Full Docs

`Graphs.LinAlg`

— Module`LinAlg`

A package for using the type system to check types of graph matrices.

`Graphs.LinAlg.Adjacency`

— Type`Adjacency{T}`

The core Adjacency matrix structure. Keeps the vertex degrees around. Subtypes are used to represent the different normalizations of the adjacency matrix. Laplacian and its subtypes are used for the different Laplacian matrices.

Adjacency(lapl::Laplacian) provides a generic function for getting the adjacency matrix of a Laplacian matrix. If your subtype of Laplacian does not provide a field A for the Adjacency instance, then attach another method to this function to provide an Adjacency{T} representation of the Laplacian. The Adjacency matrix here is the final subtype that corresponds to this type of Laplacian.

`Graphs.LinAlg.AveragingAdjacency`

— Type`AveragingAdjacency{T}`

The matrix whose action is to average over each neighborhood.

`Graphs.LinAlg.AveragingLaplacian`

— Type`AveragingLaplacian{T}`

Laplacian version of the AveragingAdjacency matrix.

`Graphs.LinAlg.CombinatorialAdjacency`

— Type`CombinatorialAdjacency{T,S,V}`

The standard adjacency matrix.

`Graphs.LinAlg.GraphMatrix`

— Type`GraphMatrix{T}`

An abstract type to allow opertions on any type of graph matrix

`Graphs.LinAlg.Noop`

— Type`Noop`

A type that represents no action.

**Implementation Notes**

- The purpose of
`Noop`

is to help write more general code for the

different scaled GraphMatrix types.

`Graphs.LinAlg.NormalizedAdjacency`

— Type`NormalizedAdjacency{T}`

The normalized adjacency matrix is $\hat{A} = D^{-1/2} A D^{-1/2}$. If A is symmetric, then the normalized adjacency is also symmetric with real eigenvalues bounded by [-1, 1].

`Graphs.LinAlg.NormalizedLaplacian`

— Type`NormalizedLaplacian{T}`

The normalized Laplacian is $\hat{L} = I - D^{-1/2} A D^{-1/2}$. If A is symmetric, then the normalized Laplacian is also symmetric with positive eigenvalues bounded by 2.

`Graphs.LinAlg.StochasticAdjacency`

— Type`StochasticAdjacency{T}`

A transition matrix for the random walk.

`Graphs.LinAlg.StochasticLaplacian`

— Type`StochasticLaplacian{T}`

Laplacian version of the StochasticAdjacency matrix.

`Graphs.LinAlg.degrees`

— Method`degrees(adjmat)`

Return the degrees of a graph represented by the `CombinatorialAdjacency`

`adjmat`

.

`Graphs.LinAlg.degrees`

— Method`degrees(graphmx)`

Return the degrees of a graph represented by the graph matrix `graphmx`

.

`Graphs.LinAlg.symmetrize`

— Function`symmetrize(adjmat, which=:or)`

Return a symmetric version of graph (represented by `CombinatorialAdjacency`

`adjmat`

) as a `CombinatorialAdjacency`

. `which`

may be one of `:triu`

, `:tril`

, `:sum`

, or `:or`

. Use `:sum`

for weighted graphs.

**Implementation Notes**

Only works on `Adjacency`

because the normalizations don't commute with symmetrization.

`Graphs.LinAlg.symmetrize`

— Function`symmetrize(A::SparseMatrix, which=:or)`

Return a symmetric version of graph (represented by sparse matrix `A`

) as a sparse matrix. `which`

may be one of `:triu`

, `:tril`

, `:sum`

, or `:or`

. Use `:sum`

for weighted graphs.

`Graphs.LinAlg.adjacency_matrix`

— Function`adjacency_matrix(g[, T=Int; dir=:out])`

Return a sparse adjacency matrix for a graph, indexed by `[u, v]`

vertices. Non-zero values indicate an edge from `u`

to `v`

. Users may override the default data type (`Int`

) and specify an optional direction.

**Optional Arguments**

`dir=:out`

: `:in`

, `:out`

, or `:both`

are currently supported.

**Implementation Notes**

This function is optimized for speed and directly manipulates CSC sparse matrix fields.

`Graphs.LinAlg.adjacency_spectrum`

— Function`adjacency_spectrum(g[, T=Int; dir=:unspec])`

Return the eigenvalues of the adjacency matrix for a graph `g`

, indexed by vertex. Default values for `T`

are the same as those in `adjacency_matrix`

.

**Optional Arguments**

`dir=:unspec`

: Options for `dir`

are the same as those in `laplacian_matrix`

.

**Performance**

Converts the matrix to dense with $nv^2$ memory usage.

**Implementation Notes**

Use `eigvals(Matrix(adjacency_matrix(g, args...)))`

to compute some of the eigenvalues/eigenvectors.

`Graphs.LinAlg.incidence_matrix`

— Function`incidence_matrix(g[, T=Int; oriented=false])`

Return a sparse node-arc incidence matrix for a graph, indexed by `[v, i]`

, where `i`

is in `1:ne(g)`

, indexing an edge `e`

. For directed graphs, a value of `-1`

indicates that `src(e) == v`

, while a value of `1`

indicates that `dst(e) == v`

. Otherwise, the value is `0`

. For undirected graphs, both entries are `1`

by default (this behavior can be overridden by the `oriented`

optional argument).

If `oriented`

(default false) is true, for an undirected graph `g`

, the matrix will contain arbitrary non-zero values representing connectivity between `v`

and `i`

.

`Graphs.LinAlg.laplacian_matrix`

— Method`laplacian_matrix(g[, T=Int; dir=:unspec])`

Return a sparse Laplacian matrix for a graph `g`

, indexed by `[u, v]`

vertices. `T`

defaults to `Int`

for both graph types.

**Optional Arguments**

`dir=:unspec`

: `:unspec`

, `:both`

, :in`, and`

:out`are currently supported. For undirected graphs,`

dir`defaults to`

:out`; for directed graphs,`

dir`defaults to`

:both`.

`Graphs.LinAlg.laplacian_spectrum`

— Function`laplacian_spectrum(g[, T=Int; dir=:unspec])`

Return the eigenvalues of the Laplacian matrix for a graph `g`

, indexed by vertex. Default values for `T`

are the same as those in `laplacian_matrix`

.

**Optional Arguments**

`dir=:unspec`

: Options for `dir`

are the same as those in `laplacian_matrix`

.

**Performance**

Converts the matrix to dense with $nv^2$ memory usage.

**Implementation Notes**

Use `eigvals(Matrix(laplacian_matrix(g, args...)))`

to compute some of the eigenvalues/eigenvectors.

`Graphs.LinAlg.spectral_distance`

— Function`spectral_distance(G₁, G₂ [, k])`

Compute the spectral distance between undirected n-vertex graphs `G₁`

and `G₂`

using the top `k`

greatest eigenvalues. If `k`

is ommitted, uses full spectrum.

**References**

- JOVANOVIC, I.; STANIC, Z., 2014. Spectral Distances of Graphs Based on their Different Matrix Representations