**Background**

I am currently reading "Modularity and community structure in networks" (2006) by Newman `[1]`.

In it, he derives a score for the modularity of a graph that, intuitively, is based on finding a division for the vertices, so that there are as many "unexpected" `[2]` edges as possible between vertices in the same group.

**Relevant Facts and Definitions**

Let $d_i$ be the degree of node $i$. Let $m$ be the number of edges. Then the *expected number of edges* between nodes $i$ and $j$ is defined as
$$E_{ij} := \frac{d_i d_j}{2m}.$$

For now, we only consider a partition into two communities. Let $s_i = 1$ iff node $i$ is in community $A$, $-1$ else.

Then, we can define a modularity score $Q$ of a partition based on the difference between the number of edges in a partition and the expected number of edges from a random graph.
$$
Q := \sum_{i,j} (A_{ij} - E_{ij}) s_i s_j
.$$

With $B:= A_{ij} - E_{ij}$ and $s := (s_1, ..., s_n)$, we can also write this as
$$
Q = s^T B s
.$$

**Question**

The next sentence is the one I don't understand.

> Given [this definition of $Q$] we proceed by writing $s$ as a linear
> combination of the normalised eigenvectors $u_i$ of $B$ so that 
> $s = \sum_{i=1}^{n} a_i u_i$ with $a_i = u_i^T s$.

I can see that $B$ has $n$ linearly independent Eigenvectors which thus form a basis. Where I'm completely lost is why we can write $s$ like so and why it is relevant that the $u_i$ are normalised.

**What I've tried**

I've spent some time trying to write down the expressions in different way but I could never find a way so that $s = \sum_{i=1}^{n} (u_i^T s) u_i$.

I've checked whether other facts presented in the paper up to this point might be relevant but I just can't see which would be. I've tried reading on to make more sense of it but there's not much more.

I've looked at questions like [this one][1] but I couldn't find anything I could apply.

I think I am really just lacking some very basic Linear Algebra ingredient here. Would be great if someone could help me out!

---

**Edit**: I was given the hint that this has to do with the [Gram-Schmidt process](https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process) and that $u_i^Ts$ is the inner product of $u_i$ and $s$. 

In fact, $\{u_1, ..., u_n\}$ form an orthonormal basis and [in the corresponding Wikipedia article][2], we I found exactly the statement in question. 

I will write a proper answer about this when I have obtained the necessary background knownledge.

---

**References**

`[1]` Newman, 2006 http://www.pnas.org/content/103/23/8577.full.pdf

`[2]` https://mathoverflow.net/questions/212761/modularity-in-a-graph-definition-of-the-random-component


  [1]: https://math.stackexchange.com/questions/1064016/linear-combination-of-eigenvectors-corresponding-to-the-same-eigenvalue?rq=1
  [2]: https://en.wikipedia.org/wiki/Orthonormal_basis