> For the complete documentation index, see [llms.txt](https://julienbeaulieu.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://julienbeaulieu.gitbook.io/wiki/sciences/math/linear-algebra/graphs-orthogonality-least-squares.md).

# Orthogonality

### Graphs

Graphs, not in the sens of calculus and lines. 1 example: if 1 person is a node and the edges is friendship. Usually the max distance is 6 degrees of separation. These are applications of linear algebra.

Ex:

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0NaZunqxnToG6bzAZ%2Fimage.png?alt=media\&token=4e3e0fb5-ebe0-475a-a9b5-f12b45cb80a6)

I need to give a direction to the edges. For example current flowing on the edges, i'll know the direction if its positive of negative. 

The incidence matrix for this graph is:

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0Nw_JyvsZk_bcwJsd%2Fimage.png?alt=media\&token=d9692df5-8372-4bd0-94d5-826d560b751d)

Let's stop at row 3 for a second because edges 1 2 and 3 form a loop. They correspond to linearly dependent rows. Real matrices from real problems have structure.  

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0OCkWc-pEzqm_lmTi%2Fimage.png?alt=media\&token=22811ece-7371-4e7c-bd8a-986307f61dfc)

Let's ask regular matrices questions. 

Nullspace? Are the 4 cols independent or dependent. Let's solve Ax=0.

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0PT0vVH7-5w5m5MTK%2Fimage.png?alt=media\&token=b61a163b-2a10-40c5-846c-6632d25b9d8c)

So we've created a matrix that computes the differences across every edge. The differences in potential. In electricity, potential differences is what makes current flow, it's what makes things happen. 

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0PqtNT_0ga5rbdkHH%2Fimage.png?alt=media\&token=3a73f6e4-2f02-4072-8571-5b0e45ba6e1b)

The null space is: 

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0Q7zKC-Xb45bxfK_x%2Fimage.png?alt=media\&token=db78b125-5857-4524-8d44-18ce50166c91)

dim N(A) = 1. The rank is n - r = 3. Any 3 potential are independent, and typically we ground that node, we make it 0. 

The null spaces means that the potentials can only be determined up to a constant. 

What is the nullspace of A T? because A T y = 0 is probably the most fundamental equation in applied math.  

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0ToGVe82uqaTOOJR8%2Fimage.png?alt=media\&token=0d38d347-b14e-4782-8d9b-ce3f66a0ea47)

Let's find a basis for this nullspace. 

Now we can find a C that gives us the relation with potentials and the current: that's actually Ohm's law. 

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0UhCgyYljemslH8-5%2Fimage.png?alt=media\&token=21699563-9d1a-4066-832e-3e2b29b1128d)

So back to A transpose. The equation from A becomes: (and we can see why on the graph). 

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0VMsAmSyx3XFoHkJg%2Fimage.png?alt=media\&token=25a755d8-697d-441b-90a8-10119806daea)

What is a basis: We know we'll have 2 vectors because dim = 2. Any current around a loop satisfies the current law. 

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0WHEMvONMafGzvq2n%2Fimage.png?alt=media\&token=6828f692-ce6b-4b34-95e2-63c056ea07da)

A graph without a loop is called tree. 

We have Euler's formula:

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Lf0A-NMrH2xM_0SGMuT%2F-Lf0XsaHnJdiy6mQgRwy%2Fimage.png?alt=media\&token=2f7d0940-dbd0-4428-a536-49ccfee6600b)

###

### Gram-Schmidt algorithm

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LelSNPA3kzqzMlwdWrP%2F-LelUpt3XWC1hxY9QTYz%2Fimage.png?alt=media\&token=7c6ce593-7d72-4587-bc9b-4d7dd1e2d279)

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LelSNPA3kzqzMlwdWrP%2F-LelUtCtc7x_F8VmiuI-%2Fimage.png?alt=media\&token=78ff4141-7328-4afd-8d36-6e9f071dfd70)

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LelSNPA3kzqzMlwdWrP%2F-LelaD1Ep0i2hof7_2SG%2Fimage.png?alt=media\&token=27984011-b95b-41b7-926f-04386fe2cb8e)

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LelSNPA3kzqzMlwdWrP%2F-LelecE02gCNf-SvAoDO%2Fimage.png?alt=media\&token=92c14d3d-a04b-4785-9123-534c06629bee)

![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LelSNPA3kzqzMlwdWrP%2F-LelevnLR6EGrmQuIKag%2Fimage.png?alt=media\&token=a7c06c59-747a-4935-bad7-371dadc2f145)

###