Generally with any definition in graph theory, there is a corresponding definition for the adjacency matrix variation of graphs.
For example, a graph isomorphism is a mapping between graphs $A$ and $B$ that preserves edge connectivity and non-connectivity. The adjacency matrix definition is $A \cong B \iff \sigma A \sigma^* = B$, where $\sigma$ is a permutation matrix.
Is there a similar definition from a graph homomorphism? A homomorphism, $\phi$ between $A$ and $B$ is a mapping that preserves node connectivity, but not necessarily non-connectivity.
Best Answer
You can do something here, but it's not great.
For the isomorphism, we describe a bijection between $V(G)$ and $V(H)$ by its permutation matrix. For the homomorphism, we have a function $f \colon V(G) \to V(H)$, which we can also describe by a matrix $F$ such that $F_{ij} = 1$ if $f$ maps the $i^{\text{th}}$ vertex of $A$ to the $j^{\text{th}}$ vertex of $B$. I will assume $V(G) = \{1,\dots,n\}$ and $V(H) = \{1,\dots,m\}$ just so we can say $F_{ij}=1 \iff f(i)=j$. Note that $F$ is not even square; in general, it is an $n \times m$ matrix.
If $A(G)$ and $A(H)$ are the adjacency matrices of $G$ and $H$, then $F A(H) F^{\mathsf T}$ is the matrix whose $(i,j)$-th entry is the sum of all products of the form $F_{ik} A(H)_{kl} F_{jl}$. We have $F_{ik}=1$ only if $k = f(i)$, and $F_{jl}=1$ only if $l = f(j)$, so actually $F A(H) F^{\mathsf T}$ is the matrix whose $(i,j)$-th entry is equal to $1$ if and only if $f(i)$ is adjacent to $f(j)$.
For the function $f$ to be a homomorphism, we want $f(i)$ to be adjacent to $f(j)$ whenever $i$ is adjacent to $j$. This is described by the adjacency matrix inequality $$A(G) \le F A(H) F^{\mathsf T}.$$ By this, I mean that every entry of $A(G)$ is less than or equal to the corresponding entry of $F A(H) F^{\mathsf T}$.