# Creating nearest neighbors Laplacian matrix

I want to create a general formula for an $N \times N$ nearest neighbors Laplacian matrix such that I can write an mfile in MATLAB to compute the matrix for given $N$.

The nearest neighbors Laplacian matrix is of the below form

$$L=\left[ \begin{array}{ccc} -2 & 1 & 0 & \cdots & 0 & 1\\ 1 & -2 & 1 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & 1 & -2 & 1\\ 1 & 0 & \cdots & 0 & 1 & -2\\ \end{array} \right].$$

where the main diagonal elements are all $-2$ and we have two elements of $1$ before and after each element in the main diagonal.

Would appreciate any help...

I might be misreading what you have written as the $L$ matrix, but I believe you can use:

L = gallery('tridiag',ones(1,N-1),-2*ones(1,N),ones(1,N-1));

This will return the tridiaganol matrix in sparse form. You can wrap it in full() to convert it to a standard matrix. Then you can manually change the top and bottom corners to 1.

Let me know if this works or if I've misunderstood the form of L.

• You can also set the corners within the sparse representation, if desired. – Ian Jun 8 '16 at 12:54
• @Ian, absolutely, and that is necessary if the matrix is too large to create in full form. – David Jun 8 '16 at 12:58

Another way of doing this for full matrices is:

>> N=5;
>> L=diag(-2*ones(1,N),0)+diag(ones(1,N-1),1)+diag(ones(1,N-1),-1)
L =

-2   1   0   0   0
1  -2   1   0   0
0   1  -2   1   0
0   0   1  -2   1
0   0   0   1  -2

>> L(1,N)=1
L =

-2   1   0   0   1
1  -2   1   0   0
0   1  -2   1   0
0   0   1  -2   1
0   0   0   1  -2

>> L(N,1)=1
L =

-2   1   0   0   1
1  -2   1   0   0
0   1  -2   1   0
0   0   1  -2   1
1   0   0   1  -2

>>

• If N is large, this implementation takes appreciably longer. For example, N=10000, using the full(gallery) function takes on the order of 1e-2 seconds (on my machine), and this takes on the order of 1 second. Not sure if that matters or not. And for larger matrices, the gallery will let you generate it in sparse form as written, which may be convenient. – David Jun 8 '16 at 12:57

That symmetric matrix is almost a tridiagonal Toeplitz matrix. Hence,

r = [-2, 1, zeros(1,n-2)];
L = toeplitz(r);


Update now the northeast and southwest corners:

L(1,n) = 1;
L(n,1) = 1;