# Linear Subspaces

We provide built-in data structures to work with (affine) linear subspaces $L$ where $L$ can be represented in either *extrinsic coordinates* $x$ with $L = \{ x | Ax = b \}$ or in *intrinsic coordinates* $u$ with $L = \{ Bu+p | u \}$.

## Coordinates

To specify which coordinates are given / expected the following can be used:

`HomotopyContinuation.Coordinates`

— Type`Coordinates`

A type used for encoding the used coordinates and for performing coordinate changes.

Currently supported coordinates are:

`HomotopyContinuation.Intrinsic`

— Constant`Intrinsic <: Coordinates`

Indicates the use of the intrinsic description of an (affine) linear subspace. See also `IntrinsicDescription`

.

`HomotopyContinuation.Extrinsic`

— Constant`Extrinsic <: Coordinates`

Indicates the use of the extrinsic description of an (affine) linear subspace. See also `ExtrinsicDescription`

.

## Constructors

`HomotopyContinuation.LinearSubspace`

— Type`LinearSubspace(A, b)`

An $m$-dimensional (affine) linear subspace $L$ in $n$-dimensional space given by the extrinsic description $L = \{ x | A x = b \}$.

```
julia> A = LinearSubspace([1 0 3; 2 1 3], [5, -2])
1-dim. (affine) linear subspace {x|Ax=b} with eltype Float64:
A:
2×3 Array{Float64,2}:
1.0 0.0 3.0
2.0 1.0 3.0
b:
2-element Array{Float64,1}:
5.0
-2.0
julia> dim(A)
1
julia> codim(A)
2
julia> ambient_dim(A)
3
```

A `LinearSubspace`

holds always its `extrinsic`

description, see also `ExtrinsicDescription`

, as well as its `intrinsic`

description, see `IntrinsicDescription`

.

```
julia> intrinsic(A)
IntrinsicDescription{Float64}:
A:
3×1 Array{Float64,2}:
-0.6882472016116853
0.6882472016116853
0.22941573387056186
b₀:
3-element Array{Float64,1}:
-3.0526315789473677
-3.947368421052632
2.684210526315789
```

A `LinearSubspace`

can be evaluated with either using `Intrinsic`

or `Extrinsic`

coordinates.

```
julia> u = [0.5]
1-element Array{Float64,1}:
0.5
julia> x = A(u, Intrinsic)
3-element Array{Float64,1}:
-3.3967551797532103
-3.6032448202467893
2.79891839325107
julia> A(x, Extrinsic)
2-element Array{Float64,1}:
0.0
0.0
```

To change the used coordinates you can use `coord_change`

.

```
julia> coord_change(A, Extrinsic, Intrinsic, x)
1-element Array{Float64,1}:
0.49999999999999994
```

`HomotopyContinuation.ExtrinsicDescription`

— Type`ExtrinsicDescription(A, b)`

Extrinsic description of an $m$-dimensional (affine) linear subspace $L$ in $n$-dimensional space. That is $L = \{ x | A x = b \}$. Note that internally `A`

and `b`

will be stored such that the rows of `A`

are orthonormal.

`HomotopyContinuation.IntrinsicDescription`

— Type`IntrinsicDescription(A, b₀)`

Intrinsic description of an $m$-dimensional (affine) linear subspace $L$ in $n$-dimensional space. That is $L = \{ u | A u + b₀ \}$. Here, $A$ and $b₀$ are in orthogonal coordinates. That is, the columns of $A$ are orthonormal and $A' b₀ = 0$.

### Functions

`HomotopyContinuation.ambient_dim`

— Function`ambient_dim(A::LinearSubspace)`

Dimension of ambient space of the (affine) linear subspace `A`

.

`HomotopyContinuation.codim`

— Function`codim(A::ExtrinsicDescription)`

Codimension of the (affine) linear subspace `A`

.

`codim(A::IntrinsicDescription)`

Codimension of the (affine) linear subspace `A`

.

`codim(A::LinearSubspace)`

Codimension of the (affine) linear subspace `A`

.

`codim(W::WitnessSet)`

The dimension of the algebraic set encoded by the witness set.

`HomotopyContinuation.coord_change`

— Function`coord_change(A::LinearSubspace, C₁::Coordinates, C₂::Coordinates, p)`

Given an (affine) linear subspace `A`

and a point `p`

in coordinates `C₁`

compute the point `x`

describing p in coordinates `C₂`

.

**Example**

```
julia> A = LinearSubspace([1 0 3; 2 1 3], [5, -2]);
julia> u = [1.25];
julia> x = coord_change(A, Intrinsic, Extrinsic, u)
3-element Array{Float64,1}:
-3.9129405809619744
-3.087059419038025
2.9709801936539915
julia> A(x, Extrinsic)
2-element Array{Float64,1}:
0.0
0.0
julia> x - A(u, Intrinsic)
3-element Array{Float64,1}:
0.0
0.0
0.0
```

`HomotopyContinuation.dim`

— Function`dim(A::ExtrinsicDescription)`

Dimension of the (affine) linear subspace `A`

.

`dim(A::IntrinsicDescription)`

Dimension of the (affine) linear subspace `A`

.

`dim(A::LinearSubspace)`

Dimension of the (affine) linear subspace `A`

.

`dim(W::WitnessSet)`

The dimension of the algebraic set encoded by the witness set.

`HomotopyContinuation.intrinsic`

— Function`intrinsic(A::LinearSubspace)`

Obtain the intrinsic description of `A`

, see also `IntrinsicDescription`

.

`HomotopyContinuation.is_linear`

— Function`is_linear(L::LinearSubspace)`

Returns `true`

if the space is proper linear subspace, i.e., described by `L = { x | Ax = 0 }.

`HomotopyContinuation.extrinsic`

— Function`extrinsic(A::LinearSubspace)`

Obtain the extrinsic description of `A`

, see also `ExtrinsicDescription`

.

`HomotopyContinuation.geodesic`

— Function`geodesic(A::LinearSubspace, B::LinearSubspace)`

Returns the geodesic $γ(t)$ connecting `A`

and `B`

in the Grassmanian $Gr(k+1,n+1)$ where $k$ is the dimension of $A$ and $n$ is the ambient dimension. See also Corollary 4.3 in ^{[LKK19]}.

`HomotopyContinuation.geodesic_distance`

— Function`geodesic_distance(A::LinearSubspace, B::LinearSubspace)`

Compute the geodesic distance between `A`

and `B`

in the affine Grassmanian `Graff(k, n)`

where `k = dim(A)`

and `n`

is the amebient dimension. This follows the derivation in ^{[LKK19]}.

`HomotopyContinuation.rand_subspace`

— Function`rand_subspace(n::Integer; dim | codim, affine = true, real = false)`

Generate a random `LinearSubspace`

with given dimension `dim`

or codimension `codim`

(one of them has to be provided) in ambient space of dimension `n`

. If `real`

is `true`

, then the extrinsic description is real. If `affine`

then an affine linear subspace is generated. The subspace is generated by drawing each entry of the extrinsic description indepdently from a normal distribuation using `randn`

.

`rand_subspace(x::AbstractVector; dim | codim, affine = true)`

Generate a random `LinearSubspace`

with given dimension `dim`

or codimension `codim`

(one of them has to be provided) in ambient space of dimension `length(x)`

going through the given point `x`

.

**Example**

Construction of a general random subspace:

```
julia> rand_subspace(3; dim = 1)
1-dim. (affine) linear subspace {x|Ax=b} with eltype Complex{Float64}:
A:
2×3 Array{Complex{Float64},2}:
-1.73825+1.27987im -0.0871343+0.840408im -0.551957+0.106397im
-0.597132-0.343965im -0.122543-0.172715im -1.04949+0.370917im
b:
2-element Array{Complex{Float64},1}:
0.47083334430689394 + 0.8099804422599071im
-0.12018696822943896 + 0.11723026326952792im
julia> rand_subspace(4; codim = 1)
3-dim. (affine) linear subspace {x|Ax=b} with eltype Complex{Float64}:
A:
1×4 Array{Complex{Float64},2}:
0.345705+0.0893881im -0.430867-0.663249im 0.979969-0.569378im -0.29722-0.192493im
b:
1-element Array{Complex{Float64},1}:
0.7749708228192062 + 0.9762873764567546im
```

`HomotopyContinuation.translate`

— Function`translate(L::LinearSubspace, δb, ::Coordinates = Extrinsic)`

Translate the (affine) linear subspace `L`

by `δb`

.

`Base.intersect`

— Method`Base.intersect(L₁::LinearSubspace, L₂::LinearSubspace)`

Intersect the two given linear subspaces. Throws an `ErrorException`

if the intersection is the sum of the codimensions is larger than the ambient dimension.

- LKK19Lim, Lek-Heng, Ken Sze-Wai Wong, and Ke Ye. "Numerical algorithms on the affine Grassmannian." SIAM Journal on Matrix Analysis and Applications 40.2 (2019): 371-393
- LKK19Lim, Lek-Heng, Ken Sze-Wai Wong, and Ke Ye. "Numerical algorithms on the affine Grassmannian." SIAM Journal on Matrix Analysis and Applications 40.2 (2019): 371-393.