mat_help

import java.util.ArrayList;
import java.util.Arrays;



public class mat_help {
    public final double[][] M;


    public double[] characteristicPolynomialCoefficients(){
        int n =  M[0].length;
        double[] b = new double[n+1];
        double[] T = new double[n];
        mat_help m = mat_help.I(n);
        for(int i=0;i<n;i++){
            m = m.mul(this);
            T[i] = m.trace();
        }
        b[0] = (n%2==0)? 1 : -1;
        for(int i=1;i<n+1;i++){
            double s = 0;
            for(int j=i-1;j>=0;j--){
                s += b[j]*T[i-j-1];
            }
            b[i] = -s/i;
        }
        return b;
    }

    public static mat_help I(int n){
        mat_help m = new mat_help(n,n);
        for(int i=0;i<n;i++){
            m.M[i][i] = 1;
        }
        return m;
    }

    public mat_help mul(mat_help b){
        mat_help m = new mat_help(M.length, M[0].length);
        for(int i=0;i< M.length;i++){
            for(int j=0;j< M[0].length;j++){
                double rij = 0;
                for(int ki=0;ki< M[0].length;ki++){
                    rij += M[i][ki]*b.M[ki][j];
                }
                m.M[i][j] = rij;
            }
        }
        return m;
    }

    public double trace(){
        double tr = 0;
        for(int i=0;i<M.length;i++){
            tr += M[i][i];
        }
        return tr;
    }

    public mat_help(int n, int m){
        M = new double[n][m];
    }

    public mat_help(double[][] t){
        M = new double[t.length][t[0].length];
        for(int i=0;i<t.length;i++){
            for(int j=0;j<t[i].length;j++){
                M[i][j]= t[i][j];
            }
        }
    }

    public static boolean existence(double t[], double a, double b){
        return calc(t, a)*calc(t, b)<=0;
    }

    public double[] eigenValues(){
        double[] pc = characteristicPolynomialCoefficients();
        return solve(pc);
    }

    public static double[] solve(double[] t){
        //System.out.println("t: "+Arrays.toString(t));

        if( t.length==2 )
            return new double[]{-t[1]/t[0]};
        double[] s = solve(prime(t));
        //System.out.println("s: "+Arrays.toString(s));
        int i;
        boolean increasing;
        ArrayList<Double> al = new ArrayList<>();
        if( existence(t, -1e20, s[0]) ){
            increasing = isIncreasing(t, s[0]-1, s[0]);
            al.add(dichotomieSolve(t, -1e20, s[0], increasing));
        }
        for(i=0;i<s.length-1;i++){
            if( existence(t, s[i], s[i+1]) ){
                increasing = isIncreasing(t, s[i], s[i+1]);
                al.add(dichotomieSolve(t, s[i], s[i+1], increasing));
            }
        }
        if( existence(t, s[s.length-1], 1e20) ){
            increasing = isIncreasing(t, s[s.length-1], s[s.length-1]+1);
            al.add(dichotomieSolve(t, s[s.length-1], 1e20, increasing));
        }
        double[] r = new double[al.size()]; i=0;
        //System.out.println("al: "+al);
        for(Double d: al){
            r[i] = d; i++;
        }
        return r;
    }

    public static double[] prime(double[] t){
        double[] tp = new double[t.length-1];
        for(int i=0;i<t.length-1;i++){
            tp[i] = t[i]*(t.length-1-i);
        }
        return tp;
    }

    public static boolean isIncreasing(double t[], double a, double b){
        return calc(t, a)<calc(t, b);
    }

    public static double dichotomieSolve(double t[], double a, double b, boolean increasing){
        double n = calc(t, (a+b)/2);
        if( Math.abs(n)<1e-7 )
            return (a+b)/2;
        if( increasing ){
            if( n>0 )
                return dichotomieSolve(t, a, (a+b)/2, increasing);
            else
                return dichotomieSolve(t, (a+b)/2, b, increasing);
        }else{
            if( n>0 )
                return dichotomieSolve(t, (a+b)/2, b, increasing);
            else
                return dichotomieSolve(t, a, (a+b)/2, increasing);
        }
    }

    public static double calc(double t[], double X){
        double res = 0;
        for(int k=0;k<t.length;k++){
            if( t[k]!=0 ){
                res += t[k]*Math.pow(X, t.length-1-k);
            }
        }
        return res;
    }


    public static void main(String[] args){
        mat_help A = new mat_help(new double[][]{
            {1, 0, -1},
            {0, 1, -1},
            {-1, -1, 2}
        });
        System.out.println(Arrays.toString(A.eigenValues()));
    }


}