Is it a stochastic matrix?

Question

A stochastic matrix is a matrix of probabilities used in the context of Markov chains.

A right stochastic matrix is a matrix where each row sums to 1.

A left stochastic matrix is a matrix where each column sums to 1.

A doubly stochastic matrix is a matrix where each row and each column sums to 1.

In this challenge, we will represent the probabilities in percent using integers. A row or column must in that case sum to 100 and not 1.

Your goal is to write a program or function which, given a square matrix of integers as input, outputs one of four values indicating that the matrix is either right stochastic, left stochastic, doubly stochastic or none of those.

Input

You may use any proper representation of a matrix that is natural for your language for the input. For example, a list of lists, a string of comma separated values with rows separated by linebreaks, etc.

The input matrix will always be square and will only contain non-negative integers. The input matrix will always be at least 1×1.

You may pass the input using STDIN, as a function argument, or anything similar.

Output

You must choose four distinct outputs that correspond to right stochastic, left stochastic, doubly stochastic or none of those. Those outputs must be constant regardless of what input is passed. Your program may not return different outputs for the same case, e.g. saying that any negative number corresponds to none of those is not valid.

In short, there must be a 1-to-1 correspondence between your output an the four possible cases. Some examples of those four outputs would be {1, 2, 3, 4} or {[1,0], [0,1], [1,1], [0,0]} or even {right, left, doubly, none}.

Please indicate in your answer the four outputs your program uses.

If a matrix is doubly stochastic, then you must return the output corresponding to doubly stochastic, and not right or left stochastic.

You may print the output to STDOUT, return it from a function, or anything similar.

Test cases

[100]               => Doubly stochastic

[42]                => None of those

[100  0  ]          => Doubly stochastic
[0    100]

[4   8   15]
[16  23  42]        => Left stochastic
[80  69  43]

[99  1 ]            => Right stochastic
[2   98]

[1   2   3   4 ]
[5   6   7   8 ]    => None of those
[9   10  11  12]
[13  14  15  16]

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

05AB1E, 13 11 10 bytes

Right stochastic: [0,1]
Left stochastic: [1,0]
Doubly stochastic: [1,1]
None of those: [0,0]

Dø2FOTnQPˆ

Try it online!

Explanation

D            # duplicate input
 ø           # transpose the copy
  2F         # 2 times do (once for each matrix)
    O        # sum of the rows
     TnQ     # is equal to 100
        P    # product
         ˆ   # add to global list
             # implicitly print global list at the end of the program

Answer 2

Haskell, 57 55 bytes

import Data.List
s a=all((==100).sum)<$>[transpose a,a]

Input of type (Eq a, Num a) => [[a]]. Outputs boolean list [left-stochastic, right-stochastic]

Thanks to @proudhaskeller for saving 2 bytes

Answer 3

R, 55 bytes

function(m)c(all(colSums(m)==100),all(rowSums(m)==100))

Unnamed function where m is assumed to be an R-matrix.

Output:

• [1] TRUE FALSE: Left stochastic
• [1] FALSE TRUE: Right stochastic
• [1] TRUE TRUE: Doubly
• [1] FALSE FALSE: None

Answer 4

Octave, 35 34 32 31 bytes

@(n)any([sum(n);sum(n')]-100,2)

Call it like this:

f(100)
f(42)
f([4,8,15; 16,23,42; 80,69,43])
f([99,1;2,98])
f([1,2,3,4;5,6,7,8;9,10,11,12;13,14,15,16])

Test it here.

Saved 2 bytes thanks to flawr initially, but went for another approach that was 1 byte shorter.

This outputs the following for the different cases:

0    Doubly
0    

1    None
1

0    Left
1

1    Right
0

The last ,2 would be unnecessary if single digits weren't included. Also, if this summed to 1 instead of 100 (as it could have), it would save another 4 bytes.

Answer 5

k, 21 19 bytes

{min'100=+/'(x;+x)}

Output

• 00b none
• 10b left
• 01b right
• 11b both

Example:

k)f:{min'100=+/'(x;+x)} //store function as f
k)f(100 0;98 2)
01b

edit: reduce byte count by 3 - function does not need to be enclosed in a lambda

edit: reduce bytecount by 2 - H/T @Simon Major

Answer 6

Mathematica 29 Bytes

{}⋃Tr/@#=={100}&/@{#,#}&

substituting the =U+F3C7=[\Transpose] character. This code snippet will paste correctly into Mathematica.

Same truthiness convention with {lefttruth, righttruth} as output

Answer 7

MATL, 12 bytes

sG!sv!100=XA

Output is two zero/one values. First indicates if the matrix is left-stochastic, second if it is right-stochastic.

Try it online! Or verify all test cases

s      % Implicitly input N×N matrix. Sum of each column. Gives a 1×N vector
G!     % Push input transposed
s      % Sum of each column. Gives a 1×N vector
v      % Concatenate vertically. Gives a 2×N matrix
!      % Transpose. N×2
100=   % Does each entry equal 100?
XA     % True for columns that contain only "true". Gives 1×2 vector. Implicitly display

Answer 8

Mathematica, 46 43 bytes

AllTrue[#==100&]/@Apply[Plus,{#,#},{1}]&

As with other answers, the outputs are

{False, False} for non-stochastic

{True, False} for left-stochastic

{False, True} for right-stochastic

{True, True} for doubly stochastic

Saved 3 bytes by switching to the operator form of AllTrue

Answer 9

C#, 205 203 183 bytes

Golfed:

int F(int[,]m){int x,i,j,r,c,e,w;x=m.GetLength(0);e=w=1;for(i=0;i<x;i++){r=c=0;for(j=0;j<x;j++){r+=m[i,j];c+=m[j,i];}if(r!=100)e=0;if(c!=100)w=0;}return e==1&&w==1?3:e==1?1:w==1?2:4;}

Ungolfed with comments:

    int F(int[,] m)
    {
        //x - matrix size
        //i, j - loop control variables
        //r, c - row/column sum
        //e, w - east/west, pseudo-bool values indicate right/left stochastic
        int x, i, j, r, c, e, w;
        x = m.GetLength(0);
        e = w = 1;

        for (i = 0; i < x; i++)
        {
            r = c = 0;

            for (j = 0; j < x; j++)
            {
                r += m[i, j];
                c += m[j, i];
            }

            if (r != 100)
                e = 0;

            if (c != 100)
                w = 0;
        }

        return e == 1 && w == 1 ? 3 : e == 1 ? 1 : w == 1 ? 2 : 4;
    }

Output key: 1 - right stochastic 2 - left stochastic 3 - double stochastic 4 - none

Try it: http://rextester.com/PKYS11433

EDIT1: r=0;c=0; => r=c=0;

EDIT2: Nested ternary operators. Credits goes to @Yodle.

Answer 10

PHP, 104 bytes

function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;}

An anonymous function that echos 0 => both, 1=> left, 2=> right, 3=> neither.
Use like:

php -r "$c=function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;};$c(json_decode($argv[1]));" "[[4,8,15],[16,23,42],[80,69,43]]"

A command line program version at 114 bytes:

for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;

Used like:

 php -r "for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;" "[[4,8,15],[16,23,42],[80,69,43]]"

Answer 11

Python 2, 70 64 Bytes

Nothing crazy here, just making use of splatting in zip to transpose the matrix :) The outputs are as follows:

0 - not stochastic
1 - right stochastic
2 - left stochastic
3 - doubly stochastic

And here's the code :)

k=lambda m:all(sum(x)==100for x in m)
lambda n:k(n)+2*k(zip(*n))

Answer 12

JavaScript (ES6), 83 bytes

a=>[a.some(a=>a.reduce((l,r)=>l-r,100)),a.some((_,i)=>a.reduce((l,a)=>l-a[i],100))]

Just to be contrary, not only does this output the right stoachistic result on the left, but the booleans are also inverted, so an output of [false, true] still means right stoachistic.

Answer 13

C#6, 130 bytes

using System.Linq;bool[]F(int[][]a)=>new[]{a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()==a.Length,a.All(x=>x.Sum()==100)};

{False, False} for non-stochastic
{True, False} for left-stochastic
{False, True} for right-stochastic
{True, True} for doubly stochastic

repl.it demo

Ungolfed

bool[]F(int[][]a)=>
    // Return new array of two bools. Array type is inferred from arguments
    new[]
    {
        // Left:
        // Count the no. of columns which sums up to 100
        a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()
            // Then check if no. of such columns equal to total column count
            ==a.Length,
        // Right: Do all rows sum up to 100?
        // Can't use this trick for left because no overload of All() accept Func<TSource,int,bool> like Where() does
        a.All(x=>x.Sum()==100)
    };

Answer 14

Groovy, 57

{a={it.every{it.sum()==100}};[a(it),a(it.transpose())]}​

Output

[0,0] if neither.

[1,0] if right.

[0,1] if left.

[1,1] if both.

Answer 15

Pip, 17 bytes

In an unexpected twist, this submission is a function.

{[h]=UQ$+_M[Zaa]}

Returns a list of two 0/1 values: [0 0] = not stochastic, [0 1] = left stochastic, [1 0] = right stochastic, [1 1] = doubly stochastic. Try it online!

Explanation

{               }  A function:
              a    Function argument (nested list)
           [Za ]   Create a list containing a's transpose and a
          M        Map this function to each of the above:
       $+_           Sum down the columns
     UQ              Get unique elements
 [h]=                If stochastic, the result should be [100]

Answer 16

Dyalog APL, 16 bytes

{∧/100=+/↑⍵(⍉⍵)}

{ } direct function definition (aka "dfn"), ⍵ is the argument

⍵(⍉⍵) the matrix alongside its transposition

↑ mix them into a single 2×n×n array

+/ sum along last axis, get a 2×n matrix

100= which elements are 100 (booleans are 0 1)

∧/ "and"-reduction along last axis, get 2 booleans for left,right stochastic

Answer 17

C++14, 139 136 133 130 bytes

-3 bytes for s=M.size(), -3 bytes for returning by reference parameter, -3 bytes as a unnamed lambda

[](auto M,int&r){int a,b,i,j,s=M.size();r=3;for(i=-1;++i<s;){for(j=-1,a=b=0;++j<s;a+=M[i][j],b+=M[j][i]);r&=(a==100)+2*(b==100);}}

Assumes input to be like vector<vector<int>>. Returns 3,2,1,0 for doubly, left, right, none stochastic.

Ungolfed:

auto f=
[](auto M, int& r){
  int a,b,i,j,s=M.size();
  r=3;
  for(i=-1;++i<s;){
    for(j=-1,a=b=0;++j<s;
      a+=M[i][j],
      b+=M[j][i]);
    r&=(a==100)+2*(b==100);
  }
}
;