Merge `RowEchelon.jl` into `LinearAlgebra.jl`

[blegat]

See JuliaLang/julia#9804

[duncanam]

@blegat Out of curiosity, is there any update as to if we will get rref() back into standard Julia install?

[jakewilliami]

I feel as though this wouldn't bee too tricky to implement. Is it not just a matter of copying some code over, and making sure nothing breaks? Or is there more to it?

[pranshumalik14]

Yeah, I feel that this has been neglected for a long time. Don't think it should be breaking anything as it works fine as is. Would be great to have this merged.

[blegat]

Nothing is blocking this I believe, just needs someone to make a PR copying the code from RowEchelon to this repo then I'll be happy to deprecate RowEchelon.jl

[jakewilliami]

I’m happy to do this in a couple of hours unless someone beats me to it before then! I’ve copied your code @blegat, and added a “verbose” option, in one of my packages :-) I also added a column swapping option, but this does not put a matrix into row echelon form, but rather it puts the matrix into an “equivalent” matrix (which is basically Linear Algebra for “close enough”), but unsure whether this should be added

[pranshumalik14]

Hahaha @jakewilliami I was literally also doing it right now. After some discussion here: https://julialang.zulipchat.com/#narrow/stream/137791-general/topic/rref it seems it is probably okay to have it back in the LinearAlgebra standard library. So making a PR to JuliaLang/julia

[jakewilliami]

@pranshumalik14 great, okay! If you wanted to add verbose and vverbose Keyword arguments, I’ve done that here: https://github.com/jakewilliami/CodingTheory.jl/blob/master/src/rref.jl

[pranshumalik14]

I didn't completely follow what you meant by column swapping and equivalent matrices. Are you referring to column operations? We can take this discussion to another messaging channel like Zulip/Slack if you want. Probably best to collaborate on this

[jakewilliami]

@pranshumalik14 I’m on slack :-)

[yewalenikhil65]

@blegat @pranshumalik14 i stumbled upon this issue as i was searching for a way to calculate rational basis of nullspace in julia . Didn't knew rref doesnt exist in julia.
Well, i tried creating such function using the logic adopted from null function from MATLAB built-in functions ( Copyright 1984-2017 The MathWorks, Inc.) and a julia library RowEchelon.jl. If it strengthens demand of merging RowEchelon into LinearAlgebra.jl , it would be great !
rref is definitely needed to calculate rational basis of nullspace and eigenvecs, although they might be not be orthonormalised !

using LinearAlgebra
using RowEchelon
function rational_basis_nullspace(A::AbstractVecOrMat)
"""
Function for finding rational basis of nullspace of a matrix A
Citation:
This function is re-written in Julia , based on
Built-in MATLAB function null.m ( Copyright 1984-2017 The MathWorks, Inc.)
"""
    R,pivot_cols = rref_with_pivots(A)
    m,n = size(A);
    r = length(pivot_cols);
    nopiv = collect(1:n);
    deleteat!(nopiv, pivot_cols)
    Z = zeros(n,n-r);
    if n > r
        Z[nopiv,:] = diagm(0 => ones(n-r));
        if r > 0
            Z[pivot_cols,:] = -R[1:r,nopiv];
        end
    end
    return Z
end