Consider the node-arc incidence matrix $A$ for your graph $G(V, E)$, $|V|=n$, $|E|=m$. (I will now assume that your graph is directed and connected.) Initially, $A$ is an $n \times m$ matrix (a row for each node and a column for each arc), with $1$ in the position $(v,e)$ if node $v$ is the head of arc $e$, $-1$ in the position $(v,e)$ if node $v$ is the tail of arc $e$, and zero otherwise. Usually, we assume that an arbitrary row of $A$ is deleted.
The following claims hold:
- $A$ is of full ($n-1$) row rank;
- for any set of $(n-1)$ linearly independent columns of $A$, the arcs corresponding to these columns make up a spanning tree of $G$;
- the null-space of the linear transformation $A$ is called the cycle space of $G$ and it is of dimension $m-n+1$ (the cyclomatic number of $G$);
- a basis for the cycle space is obtained as follows: for any spanning tree $T$ of $G$, each out-of-tree arc $(i,j)$ creates a unique cycle if arc $(i,j)$ is concatenated to the unique in-tree $j\to i$ (undirected) path and there are exactly $m-n+1$ such cycles;
- a simple way to obtain a cycle basis is to reorder the columns of $A$ to obtain the form $A=[B\quad N]$, where $B$ is an $(n-1)\times(n-1)$ submatrix of $A$ (recall, the columns correspond to a spanning tree), and then $\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}$ is a cycle basis where $I_{n-1}$ is the identity matrix of size $m-n+1$;
- the orthogonal subspace of the cycle space is called the cut space and it is of dimension $m - d_{\text{null space}} = n-1$;
- a basis for the cut-space is obtained as follows: for any spanning tree $T$ of $G$, any in-tree arc $e$ creates a unique cut of $G$ with some properly chosen set of out-of-tree arcs, and the incidence vectors of these cuts are linearly independent;
- a simple way to obtain a cut basis is again to write $A=[B\quad N]$ where $B$ is a $(n-1)\times(n-1)$ basis and then $\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}$ is a cut basis where $I_{n-1}$ is the identity matrix of size $n-1$
- you can check that the bases are indeed orthogonal by verifying that $\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}=0$
The proofs of the above claims can be found in the excellent textbook: Norman Biggs: "Algebraic Graph Theory", Cambridge Mathematical Library, 1994