# Graph Fourier transform definition

I have a question about the definition of the graph Fourier transform. Let me start with definition.

Let $$A$$ be the adjacency matrix of a graph $$G$$ with vertex set $$V = \{1, 2, \dots, n\}$$. The Laplacian matrix of $$G$$ is defined as $$L = D - A$$, where $$D$$ is a diagonal degree matrix with $$d_{ii} = deg(i)$$. Let $$\varphi_1, \dots, \varphi_n$$ be an orthonormal eigenbasis of $$L$$ and $$\lambda_1, \dots, \lambda_n$$ be the corresponding eigenvalues. Let $$f$$ be a $$V \rightarrow \mathbb{R}$$ function. The graph Fourier transform is defined as $$\begin{equation} \hat{f}(\lambda_i) = \langle f, \varphi_i \rangle = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation}$$

My question is: what happens if $$\lambda_i = \lambda_{i + 1}$$? It seems to me that this definition could give two different values for $$\hat{f}(\lambda_i)$$. Is it guaranteed that $$\sum\limits_{k = 1}^n f(k) \varphi_i^*(k) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k)$$?

EDIT: I have no problem with choosing an orthonormal eigenbasis even if there are eigenvalues with multiplicity bigger than $$1$$. My problem arises only after the eigenvectors are chosen. Suppose that $$\lambda_i = \lambda_{i + 1} = 3$$. Then I have two different formulas for $$\hat{f}(3)$$:

$$\begin{equation} \hat{f}(3) = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation}$$ and $$\begin{equation} \hat{f}(3) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k) \end{equation}$$

I think there are two possibilities:

1. The two quantities above are the same: $$\sum\limits_{k = 1}^n f(k) \varphi_i^*(k) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k)$$. I can't see why this would be true.

2. I misunderstand something about the definition.

• when there are degenerate eigenvalues the eigenvectors are not uniquely defined; for $d$ identical eigenvalues you have a $d$-dimensional eigenspace and you are free to choose any $d$ independent vectors in that space as your basis. – Carlo Beenakker Jun 4 '19 at 10:44
• I have no problem with choosing an orthonormal eigenbasis even if there are eigenvalues with multiplicity bigger than $1$. My problem arises only after the eigenvectors are chosen. If $\lambda_i = \lambda_{i + 1} = 3$, then I have two different formulas for $\hat{f}(3)$. I've edited the question, hope it makes my problem clearer. – Hanna Gábor Jun 4 '19 at 11:34

I saw the definition I mentioned in the question in many places. (E.g. here.) In Graph Structured Data Viewed Through a Fourier Lens the definition is different: $$\begin{equation} \hat{f}(i) = = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation}$$ This answers my question. :)